Algebraic conditions for \(t\)-tough graphs. (English) Zbl 1224.05307

Summary: We give some algebraic conditions for \(t\)-tough graphs in terms of the Laplacian eigenvalues and adjacency eigenvalues of graphs.


05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C75 Structural characterization of families of graphs
15A18 Eigenvalues, singular values, and eigenvectors
Full Text: DOI EuDML


[1] A. E. Brouwer: Toughness and spectrum of a graph. Linear Algebra Appl. 226–228 (1995), 267–271. · Zbl 0833.05048
[2] A. E. Brouwer and W. H. Haemers: Eigenvalues and perfect matchings. Linear Algebra Appl. 395 (2005), 155–162. · Zbl 1056.05097
[3] V. Chvátal: New directions in Hamiltonian graph theory in New Directions in the Theory of Graphs (F. Harary, ed.). Academic Press, New York, 1973, pp. 65–95.
[4] V. Chvátal: Tough graphs and hamiltonian circuits. Discrete Math. 306 (2006), 910–917. · Zbl 1095.05021
[5] H. Enomoto, B. Jackson and P. Katerinis: Toughness and the existence of k-factors. Journal of Graph Theory 9 (1985), 87–95. · Zbl 0598.05054
[6] W. H. Haemers: Interlacing eigenvalues and graphs. Linear Algebra Appl. 226–228 (1995), 593–616. · Zbl 0831.05044
[7] H. A. Jung: Note on Hamiltonian graphs, in Recent Advances in Graph Theory (M. Fiedler, ed.). Academia, Prague, 1975, pp. 315–321.
[8] B. Mohar: A domain monotonicity theorem for graphs and hamiltonicity. Discrete Appl. Math. 36 (1992), 169–177. · Zbl 0765.05071
[9] J. Vanden Heuvel: Hamilton cycles and eigenvalues of graphs. Linear Algebra Appl. 226–228 (1995), 723–730.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.