On graphs with the maximum number of spanning trees

✍ Scribed by Alexander K. Kelmans

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 814 KB
• Volume: 9
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/(sici)1098-2418(199608/09)9:1/2<177::aid-rsa11>3.0.co;2-l

✦ Synopsis

Let 3:; denote the set of simple graphs with n vertices and m edges, t ( G ) the number of spanning trees of a graph G , and F 2 H if t(K,\E(F))?t(K,\E(H)) for every s? max{u(F), u ( H ) } . We give a complete characterization of >-maximal (maximum) graphs in 3:; subject to m 5 n . This result contains, in particular, a complete characterization of those graphs in 3: that have the maximum number of spanning trees among all graphs in 3: subject to n(n -1 ) / 2 -n 5 k s n ( n -1)/2. We discuss and use properties of the

Laplacian polynomial L(A, G) of a graph G [8]. Because of relation t(K,\E(G,)) = s ' -~-' L ( s , G,,)

[8], the main result of the paper can also be interpreted as a characterisation of those graphs in 9:, m 5 n , having the maximum. Laplacian polynomial for every integer A 2 n . We also give an overview of some known approaches and results on this problem.