Edge-Disjoint Spanning Trees, Edge Connectivity, and Eigenvalues in Graphs

Let and denote the second largest eigenvalue and the maximum number of edge-disjoint spanning trees of a graph G, respectively. Motivated by a question of Seymour on the relationship between eigenvalues of a graph G and bounds of , Cioabă and Wong conjectured that for any integers and a d-regular graph G, if , then . They proved the conjecture for , and presented evidence for the cases when . Thus the conjecture remains open for . We propose a more general conjecture that for a graph G with minimum degree , if , then . In this article, we prove that for a graph G with minimum degree δ, each of the following holds. (i) For , if and , then . (ii) For , if and , then . Our results sharpen theorems of Cioabă and Wong and give a partial solution to Cioabă and Wong's conjecture and Seymour's problem. We also prove that for a graph G with minimum degree , if , then the edge connectivity is at least k, which generalizes a former result of Cioabă. As corollaries, we investigate the Laplacian and signless Laplacian eigenvalue conditions on and edge connectivity.