Hostname: page-component-8448b6f56d-qsmjn Total loading time: 0 Render date: 2024-04-16T10:05:31.378Z Has data issue: false hasContentIssue false
  • English
  • Français

A FORMULA FOR THE NUMBER OF SPANNING TREES IN CIRCULANT GRAPHS WITH NONFIXED GENERATORS AND DISCRETE TORI

Part of: Graph theory

Published online by Cambridge University Press:  25 August 2015

JUSTINE LOUIS
JUSTINE LOUIS*
Affiliation:
Section of Mathematics, Université de Genève, 1211 Genève 4, Switzerland email justine.louis@unige.ch
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We consider the number of spanning trees in circulant graphs of ${\it\beta}n$ vertices with generators depending linearly on $n$. The matrix tree theorem gives a closed formula of ${\it\beta}n$ factors, while we derive a formula of ${\it\beta}-1$ factors. We also derive a formula for the number of spanning trees in discrete tori. Finally, we compare the spanning tree entropy of circulant graphs with fixed and nonfixed generators.

Keywords

spanning treescirculant graphsspanning tree entropy

MSC classification

Primary: 05C05: Trees
Secondary: 05C30: Enumeration in graph theory
Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 92 , Issue 3 , December 2015 , pp. 365 - 373
Copyright
© 2015 Australian Mathematical Publishing Association Inc. 

References

Biggs, N., Algebraic Graph Theory, 2nd edn, Cambridge Mathematical Library (Cambridge University Press, Cambridge, 1993).Google Scholar
Boesch, F. T. and Prodinger, H., ‘Spanning tree formulas and Chebyshev polynomials’, Graphs Combin. 2(3) (1986), 191–200.CrossRefGoogle Scholar
Golin, M. J. and Leung, Y. C., ‘Unhooking circulant graphs: a combinatorial method for counting spanning trees and other parameters’, in: Graph-theoretic Concepts in Computer Science, Lecture Notes in Computer Science, 3353 (Springer, Berlin, 2004), 296–307.CrossRefGoogle Scholar
Golin, M. J., Leung, Y. C. and Wang, Y., ‘Counting spanning trees and other structures in non-constant-jump circulant graphs’, in: Algorithms and Computation, Lecture Notes in Computer Science, 3341 (Springer, Berlin, 2004), 508–521.CrossRefGoogle Scholar
Golin, M. J., Yong, X. and Zhang, Y., ‘The asymptotic number of spanning trees in circulant graphs’, Discrete Math. 310(4) (2010), 792–803.CrossRefGoogle Scholar
Louis, J., ‘Asymptotics for the number of spanning trees in circulant graphs and degeneratingd-dimensional discrete tori’, Ann. Comb. (2015), 1–31.Google Scholar
Lyons, R., ‘Asymptotic enumeration of spanning trees’, Combin. Probab. Comput. 14(4) (2005), 491–522.CrossRefGoogle Scholar
Zhang, Y., Yong, X. and Golin, M. J., ‘Chebyshev polynomials and spanning tree formulas for circulant and related graphs’, Discrete Math. 298(1–3) (2005), 334–364.CrossRefGoogle Scholar