## 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

### Keywords:

number of spanning trees; Fibonacci number; cycle