Edge‐Disjoint Spanning Trees,Edge Connectivity,and Eigenvalues in Graphs |
| |
| Authors: | Xiaofeng Gu Hong‐Jian Lai Ping Li Senmei Yao |
| |
| Institution: | 1. DEPARTMENT OF MATHEMATICS, UNIVERSITY OF WEST GEORGIA, CARROLLTON, GA;2. DEPARTMENT OF MATHEMATICS, WEST VIRGINIA UNIVERSITY, MORGANTOWN, WV;3. DEPARTMENT OF MATHEMATICS, BEIJING JIAOTONG UNIVERSITY, BEIJING, P. R. CHINA |
| |
| Abstract: | 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. |
| |
| Keywords: | eigenvalue adjacency matrix Laplacian Matrix signless Laplacian matrix quotient matrix edge connectivity edge‐disjoint spanning trees spanning tree packing number |
|
|
