# zbMATH — the first resource for mathematics

On the number of spanning trees of circulant graphs. (English) Zbl 0554.05019
A circulant graph $$C_ n(k_ 1,k_ 2,...,k_ m)$$ is a graph with n vetices numbered 0,1,...,n-1 and vertex j is adjacent to the 2m vertices $$j\pm k_ i$$ (mod n-1). This paper finds a (complex) formula for the number of spanning trees of a circulant graph $$C_ n(k_ 1,k_ 2,...,k_ m)$$. With this formula, the authors verify the following recent conjecture of Boesch: the number of spanning trees of $$C_ n(1,2)$$ is $$nF^ 2_ n$$, where $$F_ n$$ is the n-th Fibonacci number (with $$F_ 0=0$$, $$F_ 1=1)$$.
Reviewer: A.Tucker

##### MSC:
 05C05 Trees
##### Keywords:
circulant graph; spanning trees
Full Text:
##### References:
 [1] Ad’am A., J. Comb. Theory 2 pp 393– (1967) · doi:10.1016/S0021-9800(67)80037-1 [2] Alspach B., Discrete Math 25 pp 97– (1979) · Zbl 0402.05038 · doi:10.1016/0012-365X(79)90011-6 [3] Bauer D., The Theory and Application of Graphs pp 45– (1981) [4] Berggre J. L., Bull. Austrial. Math. Soc 7 pp 131– (1972) · Zbl 0228.05113 · doi:10.1017/S0004972700044890 [5] Boesch F., Fibonacci Quarterly 7 (1972) [6] Boesch F., Large-Scale Networks Theory and Design (1976) [7] Foesch F., Circulants and Their Connectivity (1982) [8] Elspas B., J. Comb. Theory 9 pp 297– (1970) · Zbl 0212.29602 · doi:10.1016/S0021-9800(70)80068-0 [9] Frank H., Maximally Reliable Node Weighted Graphs pp 1– (1969) · Zbl 0293.05143 [10] Harary F., Graph Theory (1969) [11] Harary F., The Maximum Connectivity of a Graph 48 pp 1142– (1962) · Zbl 0115.41003 [12] Kel’mans A. K., Automat. Remote Contr 3 pp 444– (1967) [13] Kirchhoff G., Ann. Phy. Chem 72 pp 496– (1967) [14] Moore E., J. Franklin Inst 262 pp 191– (1956) · Zbl 0123.12408 · doi:10.1016/0016-0032(56)90559-2 [15] Provan J. S., Management Science and Statistics Report pp 81– (1981) [16] Tindell R., Annals of Discrete Math 13 pp 191– (1982) [17] Tucker A., Applied Combinatorics (1980) [18] Wang, J. F. 1983. ”Ph.D. dissertation”. Stevens Institute of Technology Hoboken N.J. 07030 [19] Watkins H. E., J. Comb. Theory 8 pp 23– (1970) · Zbl 0185.51702 · doi:10.1016/S0021-9800(70)80005-9 [20] Williams G., IEEE Trans. Commun. Syst 11 pp 230– (1963) · doi:10.1109/TCOM.1963.1088748 [21] Wilkov R. S., IEEE Trans. on Circuit Theory 11 pp 158– (1969)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.