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

Vohra, R.; Washington, L.

J. Franklin Inst. 318, 349-355 (1984).

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

MSC:

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

References:

[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