1977/02/01 by Peter J. Slater
Computer Science · Physics and Astronomy · Mathematics · #semigroups and automata theory #Advanced Mathematical Theories and Applications #Advanced Combinatorial Mathematics
paper · doi:10.1080/00150517.1977.12430493
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<) = F2k-2 a n d ST(Wk) = L.2k-2- 2- Let OP J k denote the set of maximal outerplanar graphs with k vertices, of which exactly / are of degree two. Note that/I/ ^ e QP % for k> 4, and, with Gi as in Figure ,G1-(3,6) e OP §.