Toughness and spectrum of a graph. (English) Zbl 0833.05048

The author proves the following theorem: Let \(G\) be a connected non- complete regular graph of valency \(d\) and let \(\lambda\) be the maximum of the absolute values of the eigenvalues of \(G\) distinct from \(d\). Then the toughness \(t\) of \(G\) satisfies \(t> d/\lambda- 2\).


05C35 Extremal problems in graph theory
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI


[1] Alon, N., Tough Ramsey graphs without short cycles, (1993), Preprint · Zbl 0826.05039
[2] Brouwer, A.E.; Cohen, A.M.; Neumaier, A., Distance-regular graphs, (1989), Springer Heidelberg · Zbl 0747.05073
[3] Cvetković, D.M.; Doob, M.; Sachs, H., Spectra of graphs, (1979), VEB Berlin, Academic, New York, 1980
[4] Haemers, W.H., Eigenvalue techniques in design and graph theory, (1980), Reidel Dordrecht · Zbl 0429.05013
[5] Haemers, W.H., Interlacing eigenvalues and graphs, Linear algebra appl., 226-228, 593-616, (1995) · Zbl 0831.05044
[6] van den Heuvel, J., Degree and toughness conditions for cycles in graphs, () · Zbl 0840.05046
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.