Graph toughness from Laplacian eigenvalues. (English) Zbl 1511.05139
Summary: The toughness \(t(G)\) of a graph \(G=(V,E)\) is defined as \(t(G)=\min \left\lbrace \frac{|S|}{c(G-S)}\right\rbrace\), 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 N. Alon [J. Algebr. Comb. 4, No. 3, 189–195 (1995; Zbl 0826.05039)], A. E. Brouwer [Linear Algebra Appl. 226–228, 267–271 (1995; Zbl 0833.05048)], and X. Gu [Eur. J. Comb. 92, Article ID 103255, 11 p. (2021; Zbl 1458.05239)]. 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.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C42 | Density (toughness, etc.) |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C45 | Eulerian and Hamiltonian graphs |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
References:
| [1] | Alon, Noga, Tough Ramsey graphs without short cycles, J. Algebraic Combin., 4, 3, 189-195 (1995) · Zbl 0826.05039 · doi:10.1023/A:1022453926717 |
| [2] | Barahona, Mauricio; Pecora, Louis M., Synchronization in small-world systems, Physical Review Letters, 89, 5 (2002) · Zbl 1176.34045 |
| [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., 155, 10, 1336-1343 (2007) · Zbl 1119.05086 · doi:10.1016/j.dam.2007.02.002 |
| [4] | Bauer, Douglas; Broersma, Hajo; Schmeichel, Edward, Toughness in graphs—a survey, Graphs Combin., 22, 1, 1-35 (2006) · Zbl 1088.05045 · doi:10.1007/s00373-006-0649-0 |
| [5] | Bauer, Douglas; Vandenheuvel, Jan; Schmeichel, Edward, Toughness and triangle-free graphs, J. Combin. Theory Ser. B, 65, 2, 208-221 (1995) · Zbl 0835.05034 · doi:10.1006/jctb.1995.1051 |
| [6] | Brouwer, Andries E., Toughness and spectrum of a graph, Linear Algebra Appl., 226/228, 267-271 (1995) · Zbl 0833.05048 · doi:10.1016/0024-3795(95)00154-J |
| [7] | Brouwer, Andries E., Spectrum and connectivity of graphs, CWI Quarterly, 9, 1-2, 37-40 (1996) · Zbl 0872.05034 |
| [8] | Brouwer, Andries E.; Haemers, Willem H., Eigenvalues and perfect matchings, Linear Algebra Appl., 395, 155-162 (2005) · Zbl 1056.05097 · doi:10.1016/j.laa.2004.08.014 |
| [9] | Brouwer, Andries E.; Haemers, Willem H., Spectra of graphs, xiv+250 p. pp. (2012), Springer: Springer, New York · Zbl 1231.05001 · doi:10.1007/978-1-4614-1939-6 |
| [10] | Butler, Steve; Chung, Fan, Small spectral gap in the combinatorial Laplacian implies Hamiltonian, Ann. Comb., 13, 4, 403-412 (2010) · Zbl 1229.05193 · doi:10.1007/s00026-009-0039-4 |
| [11] | Chvátal, Vasek, Tough graphs and Hamiltonian circuits, Discrete Math., 5, 215-228 (1973) · Zbl 0256.05122 · doi:10.1016/0012-365X(73)90138-6 |
| [12] | Cioabă, Sebastian M., Perfect matchings, eigenvalues and expansion, C. R. Math. Acad. Sci. Soc. R. Can., 27, 4, 101-104 (2005) · Zbl 1110.05058 |
| [13] | Cioabă, Sebastian M.; Gregory, David A., Large matchings from eigenvalues, Linear Algebra Appl., 422, 1, 308-317 (2007) · Zbl 1116.05049 · doi:10.1016/j.laa.2006.10.020 |
| [14] | Cioabă, Sebastian M.; Gregory, David A.; Haemers, Willem H., Matchings in regular graphs from eigenvalues, J. Combin. Theory Ser. B, 99, 2, 287-297 (2009) · Zbl 1205.05177 · doi:10.1016/j.jctb.2008.06.008 |
| [15] | Cioabă, Sebastian M.; Gu, Xiaofeng, Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs, Czechoslovak Math. J., 66(141), 3, 913-924 (2016) · Zbl 1413.05222 · doi:10.1007/s10587-016-0300-z |
| [16] | Cioabă, Sebastian M.; Wong, Wiseley, The spectrum and toughness of regular graphs, Discrete Appl. Math., 176, 43-52 (2014) · Zbl 1298.05200 · doi:10.1016/j.dam.2013.12.004 |
| [17] | Doob, Michael; Cvetković, Dragoš, On spectral characterizations and embeddings of graphs, Linear Algebra Appl., 27, 17-26 (1979) · Zbl 0417.05025 · doi:10.1016/0024-3795(79)90028-4 |
| [18] | Ellingham, Mark N.; Zha, Xiaoya, Toughness, trees, and walks, J. Graph Theory, 33, 3, 125-137 (2000) · Zbl 0951.05068 · doi:10.1002/(SICI)1097-0118(200003)33:3<125::AID-JGT1>3.3.CO;2-O |
| [19] | Enomoto, Hikoe; Jackson, Bill; Katerinis, Panagiotis; Saito, Akira, Toughness and the existence of \(k\)-factors, J. Graph Theory, 9, 1, 87-95 (1985) · Zbl 0598.05054 · doi:10.1002/jgt.3190090106 |
| [20] | Favaron, Odile, On \(k\)-factor-critical graphs, Discuss. Math. Graph Theory, 16, 1, 41-51 (1996) · Zbl 0865.05061 · doi:10.7151/dmgt.1022 |
| [21] | Godsil, Chris D.; Newman, Mike W., Eigenvalue bounds for independent sets, J. Combin. Theory Ser. B, 98, 4, 721-734 (2008) · Zbl 1156.05041 · doi:10.1016/j.jctb.2007.10.007 |
| [22] | Goldberg, Felix, Bounding the gap between extremal Laplacian eigenvalues of graphs, Linear Algebra Appl., 416, 1, 68-74 (2006) · Zbl 1107.05059 · doi:10.1016/j.laa.2005.07.007 |
| [23] | Gu, Xiaofeng, Regular factors and eigenvalues of regular graphs, European J. Combin., 42, 15-25 (2014) · Zbl 1297.05146 · doi:10.1016/j.ejc.2014.05.007 |
| [24] | Gu, Xiaofeng, A proof of Brouwer’s toughness conjecture, SIAM J. Discrete Math., 35, 2, 948-952 (2021) · Zbl 1465.05102 · doi:10.1137/20M1372652 |
| [25] | Gu, Xiaofeng, Toughness in pseudo-random graphs, European J. Combin., 92, 11 p. pp. (2021) · Zbl 1458.05239 · doi:10.1016/j.ejc.2020.103255 |
| [26] | Gu, Xiaofeng; Liu, Muhuo, A tight lower bound on the matching number of graphs via Laplacian eigenvalues, European J. Combin., 101 (2022) · Zbl 1480.05106 · doi:10.1016/j.ejc.2021.103468 |
| [27] | Haemers, Willem H., Interlacing eigenvalues and graphs, Linear Algebra Appl., 226/228, 593-616 (1995) · Zbl 0831.05044 · doi:10.1016/0024-3795(95)00199-2 |
| [28] | Haemers, Willem H., Toughness conjecture (2020) |
| [29] | Haemers, Willem H., Hoffman’s ratio bound, Linear Algebra Appl., 617, 215-219 (2021) · Zbl 1459.05172 · doi:10.1016/j.laa.2021.02.010 |
| [30] | Jackson, Bill; Wormald, Nicholas Charles, \(k\)-walks in graphs, Australasian Journal of Combinatorics, 2, 135-146 (1990) · Zbl 0757.05074 |
| [31] | Katerinis, Panagiotis, Toughness of graphs and the existence of factors, Discrete Math., 80, 1, 81-92 (1990) · Zbl 0739.05047 · doi:10.1016/0012-365X(90)90297-U |
| [32] | Krivelevich, Michael; Sudakov, Benny, Sparse pseudo-random graphs are Hamiltonian, J. Graph Theory, 42, 1, 17-33 (2003) · Zbl 1028.05059 · doi:10.1002/jgt.10065 |
| [33] | Krivelevich, Michael; Sudakov, Benny, More sets, graphs and numbers, 15, Pseudo-random graphs, 199-262 (2006), Springer, Berlin · Zbl 1098.05075 · doi:10.1007/978-3-540-32439-3_10 |
| [34] | Liu, Bolian; Chen, Siyuan, Algebraic conditions for \(t\)-tough graphs, Czechoslovak Math. J., 60(135), 4, 1079-1089 (2010) · Zbl 1224.05307 · doi:10.1007/s10587-010-0073-8 |
| [35] | Lovász, László; Plummer, Michael D., Matching theory. Annals of Discrete Mathematics, 29, 121, xxvii+544 p. pp. (1986), North-Holland Publishing Co.: North-Holland Publishing Co., Amsterdam · Zbl 0618.05001 |
| [36] | Lu, Hongliang, Regular factors of regular graphs from eigenvalues, Electron. J. Combin., 17, 1, 12 p. pp. (2010) · Zbl 1204.05057 |
| [37] | Lu, Hongliang, Regular graphs, eigenvalues and regular factors, J. Graph Theory, 69, 4, 349-355 (2012) · Zbl 1243.05153 · doi:10.1002/jgt.20581 |
| [38] | Lu, Mei; Liu, Huiqing; Tian, Feng, Laplacian spectral bounds for clique and independence numbers of graphs, J. Combin. Theory Ser. B, 97, 5, 726-732 (2007) · Zbl 1122.05072 · doi:10.1016/j.jctb.2006.12.003 |
| [39] | O, Suil; Cioabă, Sebastian M., Edge-connectivity, eigenvalues, and matchings in regular graphs, SIAM J. Discrete Math., 24, 4, 1470-1481 (2010) · Zbl 1221.05224 · doi:10.1137/100786824 |
| [40] | Plummer, Michael D., Toughness and matching extension in graphs, Discrete Math., 72, 1-3, 311-320 (1988) · Zbl 0683.05034 · doi:10.1016/0012-365X(88)90221-X |
| [41] | Win, Sein, On a connection between the existence of \(k\)-trees and the toughness of a graph, Graphs Combin., 5, 2, 201-205 (1989) · Zbl 0673.05054 · doi:10.1007/BF01788671 |
| [42] | You, Zhifu; Liu, Bolian, On the Laplacian spectral ratio of connected graphs, Appl. Math. Lett., 25, 10, 1245-1250 (2012) · Zbl 1248.05116 · doi:10.1016/j.aml.2011.09.071 |
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.
