Edge-disjoint spanning trees and eigenvalues of regular graphs

详细信息	查看全文 | 推荐本文 |

• 作者：Sebastian M. Cioab膬 ; ¹ ; ^{cioaba@math.udel.edu} ; Wiseley Wong ^{wwong@math.udel.edu}
• 关键词：05C50 ; 15A18 ; 05C42 ; 15A42
• 刊名：Linear Algebra and its Applications
• 出版年：2012
• 期刊代码：38_00243795
• 类别：mt
• 出版时间：15 July, 2012
• 卷：437
• 期：2
• 页码：630-647
• 文件大小：456 K

摘要

Partially answering a question of Paul Seymour, we obtain a sufficient eigenvalue condition for the existence of k edge-disjoint spanning trees in a regular graph, when . More precisely, we show that if the second largest eigenvalue of a d-regular graph G is less than , then G contains at least k edge-disjoint spanning trees, when . We construct examples of graphs that show our bounds are essentially best possible. We conjecture that the above statement is true for any .