Edge‐Disjoint Spanning Trees, Edge Connectivity, and Eigenvalues in Graphs. Issue 1 (15th January 2015) - Gu, Xiaofeng; Lai, Hong‐Jian; Li, Ping; Yao, Senmei
Abstract: 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.