Graph toughness from Laplacian eigenvalues

Gu, Xiaofeng; Haemers, Willem H.

doi:10.5802/alco.197

Gu, Xiaofeng ¹; Haemers, Willem H.²

¹ Department of Computing and Mathematics University of West Georgia Carrollton, GA 30118, USA
² Department of Econometrics and Operations Research Tilburg University Tilburg, The Netherlands

Algebraic Combinatorics, Volume 5 (2022) no. 1, pp. 53-61.

Abstract

The toughness $t (G)$ of a graph $G = (V, E)$ is defined as $t (G) = min \{\frac{| S |}{c (G - S)}\}$ , in which the minimum is taken over all $S \subset V$ such that $G - S$ is disconnected, where $c (G - S)$ denotes the number of components of $G - S$ . We present two tight lower bounds for $t (G)$ in terms of the Laplacian eigenvalues and provide strong support for a conjecture for a better bound which, if true, implies both bounds, and improves and generalizes known bounds by Alon, Brouwer, and the first author. As applications, several new results on perfect matchings, factors and walks from Laplacian eigenvalues are obtained, which leads to a conjecture about Hamiltonicity and Laplacian eigenvalues.

Received: 2021-04-08
Revised: 2021-08-24
Accepted: 2021-08-25
Published online: 2022-02-28

DOI: 10.5802/alco.197

Classification: 05C42, 05C50, 05C70, 05C45
Keywords: Toughness, Laplacian eigenvalue, perfect matching, factor, Hamilton cycle

Author's affiliations:

Gu, Xiaofeng ¹; Haemers, Willem H. ²

¹ Department of Computing and Mathematics University of West Georgia Carrollton, GA 30118, USA
² Department of Econometrics and Operations Research Tilburg University Tilburg, The Netherlands

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{ALCO_2022__5_1_53_0,
     author = {Gu, Xiaofeng and Haemers, Willem H.},
     title = {Graph toughness from {Laplacian} eigenvalues},
     journal = {Algebraic Combinatorics},
     pages = {53--61},
     publisher = {MathOA foundation},
     volume = {5},
     number = {1},
     year = {2022},
     doi = {10.5802/alco.197},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.197/}
}

TY  - JOUR
AU  - Gu, Xiaofeng
AU  - Haemers, Willem H.
TI  - Graph toughness from Laplacian eigenvalues
JO  - Algebraic Combinatorics
PY  - 2022
SP  - 53
EP  - 61
VL  - 5
IS  - 1
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.197/
DO  - 10.5802/alco.197
LA  - en
ID  - ALCO_2022__5_1_53_0
ER  -

%0 Journal Article
%A Gu, Xiaofeng
%A Haemers, Willem H.
%T Graph toughness from Laplacian eigenvalues
%J Algebraic Combinatorics
%D 2022
%P 53-61
%V 5
%N 1
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/10.5802/alco.197/
%R 10.5802/alco.197
%G en
%F ALCO_2022__5_1_53_0

Gu, Xiaofeng; Haemers, Willem H. Graph toughness from Laplacian eigenvalues. Algebraic Combinatorics, Volume 5 (2022) no. 1, pp. 53-61. doi : 10.5802/alco.197. https://alco.centre-mersenne.org/articles/10.5802/alco.197/

References
Cited by

[1] Alon, Noga Tough Ramsey graphs without short cycles, J. Algebraic Combin., Volume 4 (1995) no. 3, pp. 189-195 | DOI | MR | Zbl

[2] Barahona, Mauricio; Pecora, Louis M. Synchronization in small-world systems, Physical Review Letters, Volume 89 (2002) no. 5, Paper no. 054101

[3] Bauer, Douglas; Broersma, Haitze J.; Kahl, Nathan; Morgana, Aurora; Schmeichel, Edward; Surowiec, T. Tutte sets in graphs. II. The complexity of finding maximum Tutte sets, Discrete Appl. Math., Volume 155 (2007) no. 10, pp. 1336-1343 | DOI | MR | Zbl

[4] Bauer, Douglas; Broersma, Hajo; Schmeichel, Edward Toughness in graphs—a survey, Graphs Combin., Volume 22 (2006) no. 1, pp. 1-35 | DOI | MR | Zbl

[5] Bauer, Douglas; Vandenheuvel, Jan; Schmeichel, Edward Toughness and triangle-free graphs, J. Combin. Theory Ser. B, Volume 65 (1995) no. 2, pp. 208-221 | DOI | MR

[6] Brouwer, Andries E. Toughness and spectrum of a graph, Linear Algebra Appl., Volume 226/228 (1995), pp. 267-271 | DOI | MR | Zbl

[7] Brouwer, Andries E. Spectrum and connectivity of graphs, CWI Quarterly, Volume 9 (1996) no. 1-2, pp. 37-40 SMC 50 jubilee (Amsterdam, 1996) | MR | Zbl

[8] Brouwer, Andries E.; Haemers, Willem H. Eigenvalues and perfect matchings, Linear Algebra Appl., Volume 395 (2005), pp. 155-162 | DOI | MR | Zbl

[9] Brouwer, Andries E.; Haemers, Willem H. Spectra of graphs, Universitext, Springer, New York, 2012, xiv+250 pages | DOI | MR | Zbl

[10] Butler, Steve; Chung, Fan Small spectral gap in the combinatorial Laplacian implies Hamiltonian, Ann. Comb., Volume 13 (2010) no. 4, pp. 403-412 | DOI | MR | Zbl

[11] Chvátal, Vasek Tough graphs and Hamiltonian circuits, Discrete Math., Volume 5 (1973), pp. 215-228 | DOI | MR | Zbl

[12] Cioabă, Sebastian M. Perfect matchings, eigenvalues and expansion, C. R. Math. Acad. Sci. Soc. R. Can., Volume 27 (2005) no. 4, pp. 101-104 | MR | Zbl

[13] Cioabă, Sebastian M.; Gregory, David A. Large matchings from eigenvalues, Linear Algebra Appl., Volume 422 (2007) no. 1, pp. 308-317 | DOI | MR | Zbl

[14] Cioabă, Sebastian M.; Gregory, David A.; Haemers, Willem H. Matchings in regular graphs from eigenvalues, J. Combin. Theory Ser. B, Volume 99 (2009) no. 2, pp. 287-297 | DOI | MR | Zbl

[15] Cioabă, Sebastian M.; Gu, Xiaofeng Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs, Czechoslovak Math. J., Volume 66(141) (2016) no. 3, pp. 913-924 | DOI | MR | Zbl

[16] Cioabă, Sebastian M.; Wong, Wiseley The spectrum and toughness of regular graphs, Discrete Appl. Math., Volume 176 (2014), pp. 43-52 | DOI | MR | Zbl

[17] Doob, Michael; Cvetković, Dragoš On spectral characterizations and embeddings of graphs, Linear Algebra Appl., Volume 27 (1979), pp. 17-26 | DOI | MR | Zbl

[18] Ellingham, Mark N.; Zha, Xiaoya Toughness, trees, and walks, J. Graph Theory, Volume 33 (2000) no. 3, pp. 125-137 | DOI | MR | Zbl

[19] Enomoto, Hikoe; Jackson, Bill; Katerinis, Panagiotis; Saito, Akira Toughness and the existence of $k$ -factors, J. Graph Theory, Volume 9 (1985) no. 1, pp. 87-95 | DOI | MR | Zbl

[20] Favaron, Odile On $k$ -factor-critical graphs, Discuss. Math. Graph Theory, Volume 16 (1996) no. 1, pp. 41-51 | DOI | MR | Zbl

[21] Godsil, Chris D.; Newman, Mike W. Eigenvalue bounds for independent sets, J. Combin. Theory Ser. B, Volume 98 (2008) no. 4, pp. 721-734 | DOI | MR | Zbl

[22] Goldberg, Felix Bounding the gap between extremal Laplacian eigenvalues of graphs, Linear Algebra Appl., Volume 416 (2006) no. 1, pp. 68-74 | DOI | MR | Zbl

[23] Gu, Xiaofeng Regular factors and eigenvalues of regular graphs, European J. Combin., Volume 42 (2014), pp. 15-25 | DOI | MR | Zbl

[24] Gu, Xiaofeng A proof of Brouwer’s toughness conjecture, SIAM J. Discrete Math., Volume 35 (2021) no. 2, pp. 948-952 | DOI | MR | Zbl

[25] Gu, Xiaofeng Toughness in pseudo-random graphs, European J. Combin., Volume 92 (2021), Paper no. 103255, 11 pages | DOI | MR | Zbl

[26] Gu, Xiaofeng; Liu, Muhuo A tight lower bound on the matching number of graphs via Laplacian eigenvalues, European J. Combin., Volume 101 (2022), Paper no. 103468 | DOI | MR

[27] Haemers, Willem H. Interlacing eigenvalues and graphs, Linear Algebra Appl., Volume 226/228 (1995), pp. 593-616 | DOI | MR | Zbl

[28] Haemers, Willem H. Toughness conjecture (2020) (https://www.researchgate.net/publication/348437253)

[29] Haemers, Willem H. Hoffman’s ratio bound, Linear Algebra Appl., Volume 617 (2021), pp. 215-219 | DOI | MR | Zbl

[30] Jackson, Bill; Wormald, Nicholas Charles $k$ -walks in graphs, Australasian Journal of Combinatorics, Volume 2 (1990), pp. 135-146 | Zbl

[31] Katerinis, Panagiotis Toughness of graphs and the existence of factors, Discrete Math., Volume 80 (1990) no. 1, pp. 81-92 | DOI | MR | Zbl

[32] Krivelevich, Michael; Sudakov, Benny Sparse pseudo-random graphs are Hamiltonian, J. Graph Theory, Volume 42 (2003) no. 1, pp. 17-33 | DOI | MR | Zbl

[33] Krivelevich, Michael; Sudakov, Benny Pseudo-random graphs, More sets, graphs and numbers (Bolyai Soc. Math. Stud.), Volume 15, Springer, Berlin, 2006, pp. 199-262 | DOI | MR | Zbl

[34] Liu, Bolian; Chen, Siyuan Algebraic conditions for $t$ -tough graphs, Czechoslovak Math. J., Volume 60(135) (2010) no. 4, pp. 1079-1089 | DOI | MR | Zbl

[35] Lovász, László; Plummer, Michael D. Matching theory. Annals of Discrete Mathematics, 29, North-Holland Mathematics Studies, 121, North-Holland Publishing Co., Amsterdam, 1986, xxvii+544 pages | MR | Zbl

[36] Lu, Hongliang Regular factors of regular graphs from eigenvalues, Electron. J. Combin., Volume 17 (2010) no. 1, Paper no. R159, 12 pages | MR | Zbl

[37] Lu, Hongliang Regular graphs, eigenvalues and regular factors, J. Graph Theory, Volume 69 (2012) no. 4, pp. 349-355 | DOI | MR | Zbl

[38] Lu, Mei; Liu, Huiqing; Tian, Feng Laplacian spectral bounds for clique and independence numbers of graphs, J. Combin. Theory Ser. B, Volume 97 (2007) no. 5, pp. 726-732 | DOI | MR | Zbl

[39] O, Suil; Cioabă, Sebastian M. Edge-connectivity, eigenvalues, and matchings in regular graphs, SIAM J. Discrete Math., Volume 24 (2010) no. 4, pp. 1470-1481 | DOI | MR | Zbl

[40] Plummer, Michael D. Toughness and matching extension in graphs, Discrete Math., Volume 72 (1988) no. 1-3, pp. 311-320 | DOI | MR | Zbl

[41] Win, Sein On a connection between the existence of $k$ -trees and the toughness of a graph, Graphs Combin., Volume 5 (1989) no. 2, pp. 201-205 | DOI | MR | Zbl

[42] You, Zhifu; Liu, Bolian On the Laplacian spectral ratio of connected graphs, Appl. Math. Lett., Volume 25 (2012) no. 10, pp. 1245-1250 | DOI | MR | Zbl

Cited by Sources: