Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs

DOI10.1007/S10587-016-0300-ZzbMath1413.05222arXiv1602.05922OpenAlexW2963305315MaRDI QIDQ2828824

Xiaofeng Gu, Sebastian M. Cioabă

Publication date: 26 October 2016

Published in: Czechoslovak Mathematical Journal (Search for Journal in Brave)

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

zbMATH Keywords

eigenvalueconnectivitytoughnessspectral graph theoryspanning \(k\)-tree

Mathematics Subject Classification ID

Trees (05C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Connectivity (05C40) Density (toughness, etc.) (05C42)

Related Items (21)

Spectral Bounds for the Connectivity of Regular Graphs with Given Order ⋮ The spanning k-trees, perfect matchings and spectral radius of graphs ⋮ Toughness and normalized Laplacian eigenvalues of graphs ⋮ Spanning trees of bounded degree, connectivity, toughness, and the spectrum of a graph ⋮ Eigenvalues and [a,b‐factors in regular graphs] ⋮ ℓ $\ell $‐Connectivity and ℓ $\ell $‐edge‐connectivity of random graphs ⋮ Spectral bounds for the vulnerability parameters of graphs ⋮ Graph rigidity properties of Ramanujan graphs ⋮ Sharp spectral bounds for the vertex-connectivity of regular graphs ⋮ Spectral conditions for connectivity, toughness and perfect \(k\)-matchings of regular graphs ⋮ Graph toughness from Laplacian eigenvalues ⋮ Toughness, Hamiltonicity and spectral radius in graphs ⋮ Toughness in pseudo-random graphs ⋮ Spectral conditions for graphs to be β-deficient involving minimum degree ⋮ Spectral radius and \(k\)-connectedness of a graph ⋮ Spectral conditions for some graphical properties ⋮ Spectral conditions for graph rigidity in the Euclidean plane ⋮ Thin trees in some families of distance-regular graphs ⋮ A tight lower bound on the matching number of graphs via Laplacian eigenvalues ⋮ A Proof of Brouwer's Toughness Conjecture ⋮ \(\ell\)-connectivity, integrity, tenacity, toughness and eigenvalues of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The spectrum and toughness of regular graphs
• Regular factors and eigenvalues of regular graphs
• Edge-disjoint spanning trees and eigenvalues of regular graphs
• Regular factors of regular graphs from eigenvalues
• Spanning trees: A survey
• Small spectral gap in the combinatorial Laplacian implies Hamiltonian
• Spectral conditions for edge connectivity and packing spanning trees in multigraphs
• Matchings in regular graphs from eigenvalues
• Eigenvalues and edge-connectivity of regular graphs
• On the \(\ell\)-connectivity of a graph
• On a connection between the existence of k-trees and the toughness of a graph
• Bounds on the size of graphs of given order and \(l\)-connectivity
• Tough Ramsey graphs without short cycles
• Toughness and spectrum of a graph
• Characterization of minimally \((2,l)\)-connected graphs
• Note on edge-disjoint spanning trees and eigenvalues
• Edge-disjoint spanning trees and eigenvalues of graphs
• Edge-disjoint spanning trees and eigenvalues
• Toughness in graphs -- a survey
• Tough graphs and Hamiltonian circuits.
• Regular Graphs, Eigenvalues and Regular Factors
• Algebraic conditions for t-tough graphs
• Edge-Disjoint Spanning Trees, Edge Connectivity, and Eigenvalues in Graphs
• Sparse pseudo‐random graphs are Hamiltonian
• Toughness, trees, and walks

This page was built for publication: Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs