Indexed by:
Abstract:
Let τ(G) and λ2(G) be the maximum number of edge-disjoint spanning trees and the second largest eigenvalue of a graph G, respectively. Motivated by a question of Seymour on the relationship between eigenvalues of a graph G and τ(G), Cioabǎ and Wong conjectured that for any integers k≥2, d≥2k and a d-regular graph G, if λ2(G)<d-2k-1/d+1, then τ(G)≥k. They proved this conjecture for k=2,3. Gu, Lai, Li and Yao generalized this conjecture to simple graph and conjectured that for any integer k≥2 and a graph G with minimum degree δ and maximum degree Δ, if lambda;2(G) <2δ-Δ-2k-1/δ+1 then τ(G)≥k. In this paper, we prove that λ2(G)≤δ-2k-2/kδ+1 implies τ(G)≥k and show the two conjectures hold for sufficiently large n. © 2013 Elsevier Inc. All rights reserved.
Keyword:
Reprint 's Address:
Email:
Source :
Linear Algebra and Its Applications
ISSN: 0024-3795
Year: 2014
Volume: 444
Page: 146-151
0 . 9 3 9
JCR@2014
1 . 0 0 0
JCR@2023
ESI HC Threshold:86
JCR Journal Grade:1
CAS Journal Grade:2
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: