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

Zhang, Yuanping; Yong, Xuerong; Golin, Mordecai J.

Discrete Math. 223, No. 1-3, 337-350 (2000).

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.

MSC:

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

Keywords:

matrix tree theorem; determinant; Cayley’s tree formula; number of spanning trees; circulant graphs