Please use this identifier to cite or link to this item:

Unhooking circulant graphs: A combinatorial method for counting spanning trees and other parameters

Authors Golin, Mordecai J. View this author's profile
Leung, YC
Issue Date 2004
Source Lecture Notes in Computer Science , v. 3353, 2004, p. 296-307
Summary It has long been known that the number of spanning trees in circulant graphs with fixed jumps and n nodes satisfies a recurrence relation in n. The proof of this fact was algebraic (relating the products of eigenvalues of the graphs' adjacency matrices) and not combinatorial. In this paper we derive a straightforward combinatorial proof of this fact. Instead of trying to decompose a large circulant graph into smaller ones, our technique is to instead decompose a large circulant graph into different step graph cases and then construct a recurrence relation on the step graphs. We then generalize this technique to show that the numbers of Hamiltonian Cycles, Eulerian Cycles and Eulerian Orientations in circulant graphs also satisfy recurrence relations.
ISSN 0302-9743
Language English
Format Article
Access View full-text via Web of Science
View full-text via Scopus