Edge‐Disjoint Spanning Trees, Eigenvalues, and Size of Graphs

ABSTRACT

The spanning tree packing number of a graph , written by , is defined as the maximum number of edge‐disjoint spanning trees. The study of is a classic problem in graph theory, and this parameter has important application in analyzing network robustness, routing optimization, and fault tolerance. Paul Seymour motivated the academia to establish the relationship between and eigenvalues of a connected graph. Let be the class of ‐vertex graphs with minimum degree and let denote the set of graphs of order and size admitting exactly edge‐disjoint spanning trees. Fan, Gu, and Lin [J. Graph Theory, 104 (2023) 697‐711] gave a sufficient size condition, together with its spectral analogue, to ensure that a graph satisfies under the condition . It is interesting to see that these problems are still open under the condition . In this paper, we fill this gap. Then we address an open problem posed by Fan, Gu, and Lin [J. Graph Theory, 104 (2023) 697‐711]: Determine the graphs among having maximum spectral radius. Furthermore, they conjectured that is the unique graph among attaining maximum spectral radius for and . We show that, for with is the unique graph among having maximum spectral radius. This resolves their open problem, and consequently disproves their conjecture.