×

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

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
PDF BibTeX XML Cite