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

Letλ 2 ( G )and τ ( G ) 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 τ ( G ) , Cioabă and Wong conjectured that for any integers d , k ≥ 2 and a d ‐regular graph G , ifλ 2 ( G ) < d − 2 k − 1 d + 1, then τ ( G ) ≥ k . They proved the conjecture for k = 2 , 3 , and presented evidence for the cases when k ≥ 4 . Thus the conjecture remains open for k ≥ 4 . We propose a more general conjecture that for a graph G with minimum degree δ ≥ 2 k ≥ 4 , ifλ 2 ( G ) < δ − 2 k − 1 δ + 1, then τ ( G ) ≥ k . In this article, we prove that for a graph G with minimum degree δ, each of the following holds. (i) For k ∈ { 2 , 3 } , if δ ≥ 2 k andλ 2 ( G ) < δ − 2 k − 1 δ + 1, then τ ( G ) ≥ k . (ii) For k ≥ 4 , if δ ≥ 2 k andλ 2 ( G ) < δ − 3 k − 1 δ + 1, then τ ( G ) ≥ k . 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 δ ≥ k ≥ 2 , ifλ 2 ( G ) < δ − 2 ( k − 1 ) δ + 1, 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 τ ( G ) and edge connectivity.