×

The spectrum and toughness of regular graphs. (English) Zbl 1298.05200

Summary: A. E. Brouwer [Linear Algebra Appl. 226–228, 267–271 (1995; Zbl 0833.05048)] proved that the toughness of a connected \(k\)-regular graph \(G\) is at least \(k / \lambda - 2\), where \(\lambda\) is the maximum absolute value of the non-trivial eigenvalues of \(G\). Brouwer conjectured that one can improve this lower bound to \(k / \lambda - 1\) and that many graphs (especially graphs attaining equality in the Hoffman ratio bound for the independence number) have toughness equal to \(k / \lambda\). In this paper, we improve Brouwer’s spectral bound when the toughness is small and we determine the exact value of the toughness for many strongly regular graphs attaining equality in the Hoffman ratio bound such as lattice graphs, triangular graphs, complements of triangular graphs and complements of point-graphs of generalized quadrangles. For all these graphs with the exception of the Petersen graph, we confirm Brouwer’s intuition by showing that the toughness equals \(k /(- \lambda_{\min})\), where \(\lambda_{\min}\) is the smallest eigenvalue of the adjacency matrix of the graph.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C35 Extremal problems in graph theory
05E30 Association schemes, strongly regular graphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Citations:

Zbl 0833.05048
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, N., Tough Ramsey graphs without short cycles, J. Algebraic Combin., 4, 3, 189-195 (1995) · Zbl 0826.05039
[2] Bauer, D.; Broersma, H. J.; Schmeichel, E., Toughness of graphs—a survey, Graphs Combin., 22, 1-35 (2006) · Zbl 1088.05045
[3] Bauer, D.; Broersma, H. J.; Veldman, H. J., Not every 2-tough graph is Hamiltonian, Discrete Appl. Math., 99, 317-321 (2000) · Zbl 0934.05083
[4] Bauer, D.; van den Heuvel, J.; Morgana, A.; Schmeichel, E., The complexity of recognizing tough cubic graphs, Discrete Appl. Math., 79, 35-44 (1997) · Zbl 0888.68092
[5] Bauer, D.; van den Heuvel, J.; Morgana, A.; Schmeichel, E., The complexity of toughness in regular graphs, Congr. Numer., 130, 47-61 (1998) · Zbl 0986.68531
[6] Brouwer, A. E., Toughness and spectrum of a graph, Linear Algebra Appl., 226-228, 267-271 (1995) · Zbl 0833.05048
[7] Brouwer, A. E., Connectivity and spectrum of graphs, CWI Quarterly, 9, 37-40 (1996) · Zbl 0872.05034
[8] Brouwer, A. E.; Haemers, W. H., Spectra of Graphs, 250 (2012), Springer: Springer Universitext · Zbl 1231.05001
[9] Brouwer, A. E.; Mesner, D., The connectivity for strongly regular graphs, European J. Combin., 6, 215-216 (1985) · Zbl 0607.05045
[10] Chvátal, V., Tough graphs and Hamiltonian circuits, Discrete Math., 5, 215-228 (1973) · Zbl 0256.05122
[11] Cioabă, S. M., Closed walks and eigenvalues of Abelian Cayley graphs, C. R. Acad. Sci. Paris Sér. I Math., 342, 635-638 (2006) · Zbl 1102.05031
[12] Cioabă, S. M.; Gregory, D. A.; Haemers, W. H., Matchings in regular graphs from eigenvalues, J. Combin. Theory Ser. B, 99, 287-297 (2009) · Zbl 1205.05177
[13] Godsil, C.; Royle, G., (Algebraic Graph Theory. Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207 (2001), Springer Verlag: Springer Verlag New York) · Zbl 0968.05002
[14] Haemers, W. H., Interlacing eigenvalues and graphs, Linear Algebra Appl., 226-228, 593-616 (1995) · Zbl 0831.05044
[15] Liu, B.; Chen, S., Algebraic conditions for \(t\)-tough graphs, Czechoslovak Math. J., 60, 135, 1079-1089 (2010) · Zbl 1224.05307
[16] Matthews, M. M.; Sumner, D. P., Hamiltonian results in \(K_{1, 3}\)-free graphs, J. Graph Theory, 8, 139-146 (1984) · Zbl 0536.05047
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.