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

Counting spanning trees and other structures in non-constant-jump circulant graphs

Authors Golin, Mordecai J. View this author's profile
Leung, YC
Wang, YJ
Issue Date 2004
Source Lecture Notes in Computer Science , v. 3341, 2004, p. 508-521
Summary Circulant graphs are an extremely well-studied subclass of regular graphs, partially because they model many practical computer network topologies. It has long been known that the number of spanning trees in n-node circulant graphs with constant jumps satisfies a recurrence relation in n. For the non-constant-jump case, i.e., where some jump sizes can be functions of the graph size, only a few special cases such as the Mobius ladder had been studied but no general results were known. In this note we show how that the number of spanning trees for all classes of n node circulant graphs satisfies a recurrence relation in n even when the jumps are non-constant (but linear) in the graph size. The technique developed is very general and can be used to show that many other structures of these circulant graphs, e.g., number of Hamiltonian Cycles, Eulerian Cycles, Eulerian Orientations, etc., also satisfy recurrence relations. The technique presented for deriving the recurrence relations is very mechanical and, for circulant graphs with small jump parameters, can easily be quickly implemented on a computer. We illustrate this by deriving recurrence relations counting all of the structures listed above for various circulant graphs.
ISSN 0302-9743
Language English
Format Article
Access View full-text via Web of Science
View full-text via Scopus