Counting spanning trees in the graphs of Kleitman and Golden and a generalization. (English) Zbl 0569.05016

The number of trees in a graph G on \(n+1\) vertices is, by the celebrated matrix tree theorem, given by the determinant of an \(n\times n\) matrix whose (i-th entry is 1 when G has an edge connecting the i-th and j-th vertices (for i and j between 1 and n) and i-th diagonal element given by minus the degree of the i-th vertex. The authors here use properties of circulant matrices to evaluate this determinant in the case in which the \((n+1)\times (n+1)\) matrix of which this is a cofactor, is a circulant.
Reviewer: D.Kleitman


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


[1] Kleitman, D.J.; Golden, B., Counting trees in a certain class of graphs, Am. math. monthly, Vol. 82, 40-44, (1975) · Zbl 0297.05123
[2] Harary, F., Graph theory, (1969), Addison-Wesley Reading, Mass · Zbl 0797.05064
[3] Washington, L., Introduction to cyclotomic fields, (1982), Springer New York, Heidelberg, Berlin · Zbl 0484.12001
[4] Marcus, D., Number fields, (1977), Springer New York, Heidelberg, Berlin
[5] Bedrosian, S.D., The Fibonacci numbers via trigonometric expressions, J. franklin inst., Vol. 295, 175-177, (1973) · Zbl 0298.05104
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.