𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the characterization of graphs with maximum number of spanning trees

✍ Scribed by L. Petingi; F. Boesch; C. Suffel

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
591 KB
Volume
179
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G with n nodes and e edges is said to be t-optimal if G has the maximum number of spanning trees among all graphs with the same number of nodes and edges as G. Hitherto, t-optimal graphs have been characterized for the following cases: (a) n=sp, and e=(s(s-1)/2)p 2, when s and p are positive integers, and s > 1; (b) e<<.n + 2; (c) e>~n(n -1)/2 -n/2.

In this paper we use algebraic techniques involving eigenvalues to determine t-optimal graphs for e>~n(n -1)/2 -n + 2. This range is extended to include e = n(n -1)/2 -n + 1 and e= n(n-1)/2 -n, provided n(n-1)/2 -e is a multiple of three.

πŸ“œ SIMILAR VOLUMES

On graphs with the maximum number of spa
On graphs with the maximum number of spanning trees
✍ Alexander K. Kelmans πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 814 KB

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 conta

Finding the Graph with the Maximum Numbe
Finding the Graph with the Maximum Number of Spanning Trees
✍ George Moustakides; Samuel D. Bedrosian πŸ“‚ Article πŸ“… 1980 πŸ› Elsevier Science 🌐 English βš– 328 KB

The problem is to determine the linear graph that has the maximum number of spanning trees, where only the number of nodes N and the number of branches B are prescribed. We deal with connected graphs G(N, B) obtained by deleting D branches from a complete graph KN. Our solution is for D less than or

On the asymptotic behavior of the maximu
On the asymptotic behavior of the maximum number of spanning trees in circulant graphs
✍ Lonc, Zbigniew; Parol, Krzysztof; Wojciechowski, Jacek M. πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 126 KB πŸ‘ 3 views

The following asymptotic estimation of the maximum number of spanning trees f k (n) in 2kregular circulant graphs ( k ΓΊ 1) on n vertices is the main result of this paper: )) , where

On numbers of vertices of maximum degree
On numbers of vertices of maximum degree in the spanning trees of a graph
✍ Jerzy Topp; Preben D. Vestergaard πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 611 KB

For a connected graph G, let ~-(G) be the set of all spanning trees of G and let nd(G) be the number of vertices of maximum degree in G. In this paper we show that if G is a cactus or a connected graph with p vertices and p+ 1 edges, then the set {na(T) : T C ~-(G)) has at most one gap, that is, it