Edge-disjoint spanning trees and eigenvalues of regular graphs

DOI10.1016/J.LAA.2012.03.013MaRDI QIDQ426054zbMATHOpenAlexFDO

Authors Sebastian Cioaba, Wiseley Wong

Publication date 11 June 2012

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.2245

zbMATH Keywords

eigenvalueconnectivitytoughnessedge-disjoint spanning treesedge-toughness

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05) Connectivity (05C40)

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 $kin2,3$. More precisely, we show that if the second largest eigenvalue of a $d$-regular graph $G$ is less than $d-frac2k-1d+1$, then $G$ contains at least $k$ edge-disjoint spanning trees, when $kin2,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$.

Recommendations

• Edge-disjoint spanning trees and eigenvalues
• Edge-disjoint spanning trees and eigenvalues of graphs
• Edge-disjoint spanning trees, edge connectivity, and eigenvalues in graphs
• Note on edge-disjoint spanning trees and eigenvalues
• Extremal graphs for a spectral inequality on edge-disjoint spanning trees

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• A short proof of the tree-packing theorem
• Bounds of the number of disjoint spanning trees
• Edge-Disjoint Spanning Trees of Finite Graphs
• Edge-connectivity and edge-disjoint spanning trees
• Eigenvalues and edge-connectivity of regular graphs
• Embedding spanning trees in random graphs
• Interlacing eigenvalues and graphs
• Matrix Analysis
• On the Problem of Decomposing a Graph into n Connected Factors
• On the higher-order edge toughness of a graph
• On the spanning tree packing number of a graph: A survey
• Optimal attack and reinforcement of a network
• Spanning trees: A survey
• Spectra of graphs
• Tough Ramsey graphs without short cycles
• Toughness and spectrum of a graph

Cited in

(26)

• Edge connectivity, packing spanning trees, and eigenvalues of graphs
• Extremal graphs for a spectral inequality on edge-disjoint spanning trees
• Note on edge-disjoint spanning trees and eigenvalues
• Edge-disjoint spanning trees and eigenvalues of graphs
• Edge-disjoint spanning trees and eigenvalues
• Sharp spectral bounds for the vertex-connectivity of regular graphs
• Spectral conditions for edge connectivity and spanning tree packing number in (multi-)graphs
• Connectivity and eigenvalues of graphs with given girth or clique number
• Fractional arboricity, strength and eigenvalues of graphs with fixed girth or clique number
• Spanning trees of bounded degree, connectivity, toughness, and the spectrum of a graph
• Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs.
• Spectral radius and edge‐disjoint spanning trees
• Edge-disjoint spanning trees and forests of graphs
• Spectral conditions for graph rigidity in the Euclidean plane
• Vertex-connectivity and eigenvalues of graphs
• \(l\)-connectivity, \(l\)-edge-connectivity and spectral radius of graphs
• Fractional spanning tree packing, forest covering and eigenvalues
• scientific article; zbMATH DE number 5499264 (Why is no real title available?)
• Toughness in pseudo-random graphs
• Graph rigidity properties of Ramanujan graphs
• Spanning tree packing number and eigenvalues of graphs with given girth
• The vertex connectivity and the third largest eigenvalue in regular (multi-)graphs
• Vertex-connectivity and eigenvalues of graphs with fixed girth
• Spectral conditions for edge connectivity and packing spanning trees in multigraphs
• Spectral conditions for graphs to be \(\beta\)-deficient involving minimum degree
• Edge-disjoint spanning trees, edge connectivity, and eigenvalues in graphs

This page was built for publication: Edge-disjoint spanning trees and eigenvalues of regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q426054)