Fibonacci Numbers in Tree Counts for Maximal Outerplane and Related Graphs
David W. Bange, Anthony E. Barkauskas, Peter J. Slater · The Fibonacci Quarterly · 1981
Let G denote a plane multigraph that is obtained from a maximal outerplane graph by adding a collection of multiedges. We associate with each such G an M-tree (a tree in which some vertices are designated as type M), and we observe that many such graphs can be associated with the same M-tree. Formulas for counting spanning trees are given and are used to generate some Fibonacci identities. The path Pn is shown to be the tree on n vertices whose associated graph has the maximum number of spanning trees, and a class of trees on n vertices whose associated graph yields the minimum is conjectured.