Edge‐Disjoint Spanning Trees, Edge Connectivity, and Eigenvalues in Graphs. Issue 1 (15th January 2015)

• Record Type: Journal Article
• Authors: Gu, Xiaofeng; Lai, Hong‐Jian; Li, Ping; Yao, Senmei
• Is Part Of: Journal of graph theory. Volume 81:Issue 1(2016)
• Page Start: 16
• Page End: 29
• Publication Date: 2015-01-15
• Subjects: eigenvalue -- adjacency matrix -- Laplacian Matrix -- signless Laplacian matrix -- quotient matrix -- edge connectivity -- edge‐disjoint spanning trees -- spanning tree packing number; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21857
• Languages: English
• ISSNs: 0364-9024

Abstract

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.