Fibonacci Numbers in the Count of Spanning Trees
Peter J. Slater · The Fibonacci Quarterly · 1977
Hilton [3] and Fielder [1] have presented formulas for the number of spanning trees of a labelled wheel or fan in terms of Fibonacci and Lucas numbers. Each of them has also counted thejiumber of spanning trees in one of these graphs which contain a specified edge. The purpose of this note is to generalize some of their results. The graph theory terminology used will be consistent with that in [2], Fk denotes the k th Fibonacci number, and Lk denotes the k f Lucas number. All graphs will be connected, and ST(G) will denote the number of spanning trees of labelled graph, or multigraph, G. A fan on k vertices, denoted N^, is the graph obtained from path Pk-i = 2, 3, •••, k by making vertex 1 adja— cent to every vertex oiPk--/. The wheel on k vertices, denoted W^, is obtained by adding edge (2,k) to/l/^. That is, Wk = Nk + (2,k). Aplanar qraph G is one that can be drawn in the plane so that no two edges intersect; G is outerplanar if it can be drawn in the plane so that no two edges intersect, and all its vertices lie on the same face; and a maximal outerplanar graph G is an outerplanar graph for which G + (u,v) is not outerplanar for any pair^/,1 / of vertices of G such that edge (u,v) is not already in G. For example, each fan is a maximal outerplanar graph because, as will be used in the proof of Proposition 1, an outerplanar graph on k vertices is maximal outerplanar if and only if it has 2k- 3 edges. Figure 1 Three Graphs on Six Vertices As shown in Hilton [3],ST(Nf 4, and, with Gi as in Figure \\,G1-(3,6) e OP §.