The number of spanning trees in circulant graphs. (English) Zbl 0969.05036

Summary: We develop a method for determining the exact number of spanning trees in (directed or undirected) circulant graphs. Using this method we can, for any class of circulant graphs, exhibit a recurrence relation for the number of its spanning trees. We describe the method and give examples of its use.


05C30 Enumeration in graph theory
05C05 Trees
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI