The number of spanning trees in the square of a cycle. (English) Zbl 0587.05040

Baron, G.; Prodinger, H.; Tichy, R. F.; Boesch, F. T.; Wang, J. F.

Fibonacci Q. 23, 258-264 (1985).

Let \(t(G)\) denote the number of spanning trees of a graph \(G\) and let \(F_n\) be the \(n\)th Fibonacci number defined inductively as \(F_0=0\), \(F_1=1\), \(F_n=F_{n-1}+F_{n-2}\). The authors prove that \(t(C_n^2)=nF_n^2\), where \(C_n^2\) is the square of the \(n\) vertex cycle \(C_n\).

Reviewer: H. Gerber

MSC:

05C38	Paths and cycles
05C05	Trees
05C30	Enumeration in graph theory

Keywords:

number of spanning trees; Fibonacci number; cycle