pith. sign in

arxiv: 1312.2245 · v1 · pith:KQ4TDE6Onew · submitted 2013-12-08 · 🧮 math.CO · cs.DM

Edge-disjoint spanning trees and eigenvalues of regular graphs

classification 🧮 math.CO cs.DM
keywords edge-disjointregularspanningtreeseigenvaluegraphgraphswhen
0
0 comments X
read the original abstract

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 $k\in \{2,3\}$. More precisely, we show that if the second largest eigenvalue of a $d$-regular graph $G$ is less than $d-\frac{2k-1}{d+1}$, then $G$ contains at least $k$ edge-disjoint spanning trees, when $k\in \{2,3\}$. We construct examples of graphs that show our bounds are essentially best possible. We conjecture that the above statement is true for any $k<d/2$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.