Abstract
The eigenvalues of graphs are related to many of its combinatorial properties. In his fundamental work, Fiedler showed the close connections between the Laplacian eigenvalues and eigenvectors of a graph and its vertex-connectivity and edge-connectivity.
We present some new results describing the connections between the spectrum of a regular graph and other combinatorial parameters such as its generalized connectivity, toughness, and the existence of spanning trees with bounded degree.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N. Alon: Tough Ramsey graphs without short cycles. J. Algebr. Comb. 4 (1995), 189–195.
D. Bauer, H. J. Broersma, E. Schmeichel: Toughness of graphs—a survey. Graphs Comb. 22 (2006), 1–35.
J. A. Bondy, U. S. R. Murty: Graph Theory. Graduate Texts in Mathematics 244, Springer, Berlin, 2008.
A. E. Brouwer: Spectrum and connectivity of graphs. CWI Quarterly 9 (1996), 37–40.
A. E. Brouwer: Toughness and spectrum of a graph. Linear Algebra Appl. 226/228 (1995), 267–271.
A. E. Brouwer, W. H. Haemers: Spectra of Graphs. Universitext, Springer, Berlin, 2012.
S. Butler, F. Chung: Small spectral gap in the combinatorial Laplacian implies Hamiltonian. Ann. Comb. 13 (2010), 403–412.
G. Chartrand, S. F. Kapoor, L. Lesniak, D. R. Lick: Generalized connectivity in graphs. Bull. Bombay Math. Colloq. 2 (1984), 1–6.
V. Chvátal: Tough graphs and Hamiltonian circuits. Discrete Math. 5 (1973), 215–228.
S. M. Cioabă: Eigenvalues and edge-connectivity of regular graphs. Linear Algebra Appl. 432 (2010), 458–470.
S. M. Cioabă, D. A. Gregory, W. H. Haemers: Matchings in regular graphs from eigenvalues. J. Comb. Theory, Ser. B 99 (2009), 287–297.
S. M. Cioabă, W. Wong: The spectrum and toughness of regular graphs. Discrete Appl. Math. 176 (2014), 43–52.
S. M. Cioabă, W. Wong: Edge-disjoint spanning trees and eigenvalues of regular graphs. Linear Algebra Appl. 437 (2012), 630–647.
D. P. Day, O. R. Oellermann, H. C. Swart: Bounds on the size of graphs of given order and l-connectivity. Discrete Math. 197/198 (1999), 217–223.
M. N. Ellingham, X. Zha: Toughness, trees, and walks. J. Graph Theory 33 (2000), 125–137.
M. Fiedler: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech. Math. J. 25 (1975), 619–633.
M. Fiedler: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298–305.
C. Godsil, G. Royle: Algebraic Graph Theory. Graduate Texts in Mathematics 207, Springer, New York, 2001.
X. Gu: Spectral conditions for edge connectivity and packing spanning trees in multigraphs. Linear Algebra Appl. 493 (2016), 82–90.
X. Gu: Regular factors and eigenvalues of regular graphs. Eur. J. Comb. 42 (2014), 15–25.
X. Gu: Connectivity and Spanning Trees of Graphs. PhD Dissertation, West Virginia University, 2013.
X. Gu, H.-J. Lai, P. Li, S. Yao: Edge-disjoint spanning trees, edge connectivity and eigenvalues in graphs. J. Graph Theory 81 (2016), 16–29.
X. Gu, H.-J. Lai, S. Yao: Characterization of minimally (2, l)-connected graphs. Inf. Process. Lett. 111 (2011), 1124–1129.
M. Krivelevich, B. Sudakov: Pseudo-random graphs. More Sets, Graphs and Numbers (E. Győri, ed.). Bolyai Soc. Math. Stud. 15, Springer, Berlin, 2006, pp. 199–262.
M. Krivelevich, B. Sudakov: Sparse pseudo-random graphs are Hamiltonian. J. Graph Theory 42 (2003), 17–33.
G. Li, L. Shi: Edge-disjoint spanning trees and eigenvalues of graphs. Linear Algebra Appl. 439 (2013), 2784–2789.
B. Liu, S. Chen: Algebraic conditions for t-tough graphs. Czech. Math. J. 60 (2010), 1079–1089.
Q. Liu, Y. Hong, X. Gu, H.-J. Lai: Note on edge-disjoint spanning trees and eigenvalues. Linear Algebra Appl. 458 (2014), 128–133.
Q. Liu, Y. Hong, H.-J. Lai: Edge-disjoint spanning trees and eigenvalues. Linear Algebra Appl. 444 (2014), 146–151.
H. Lu: Regular graphs, eigenvalues and regular factors. J. Graph Theory 69 (2012), 349–355.
H. Lu: Regular factors of regular graphs from eigenvalues. Electron. J. Comb. 17 (2010), Research paper 159, 12 pages.
O. R. Oellermann: On the l-connectivity of a graph. Graphs Comb. 3 (1987), 285–291.
K. Ozeki, T. Yamashita: Spanning trees: A survey. Graphs Comb. 27 (2011), 1–26.
S. Win: On a connection between the existence of k-trees and the toughness of a graph. Graphs Comb. 5 (1989), 201–205.
W. Wong: Spanning Trees, Toughness, and Eigenvalues of Regular Graphs. PhD Disser-tation, University of Delaware, 2013, available at http://pqdtopen.proquest.com/doc/1443835286.html?FMT=ABS.
Author information
Authors and Affiliations
Corresponding author
Additional information
Dedicated to the memory of Professor Miroslav Fiedler
The research of the first author was partially supported by the National Security Agency grant H98230-13-0267 and the National Science Foundation grant DMS-1600768.
Rights and permissions
About this article
Cite this article
Cioabă, S.M., Gu, X. Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs. Czech Math J 66, 913–924 (2016). https://doi.org/10.1007/s10587-016-0300-z
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10587-016-0300-z