In this paper 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 graph, exhibit a recurrence relation for the number of its spanning trees. We describe the method and give examples of its use. c 2000 Elsevier Science B.V. All rights reserved.
['Yuanping Zhang', 'Xuerong Yong', 'Mordecai J. Golin']
The number of spanning trees in circulant graphs