| Title:
|
Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs (English) |
| Author:
|
Cioabă, Sebastian M. |
| Author:
|
Gu, Xiaofeng |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
66 |
| Issue:
|
3 |
| Year:
|
2016 |
| Pages:
|
913-924 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
The eigenvalues of graphs are related to many of its combinatorial properties. In his fundamental work, Fiedler showed the close connections between the Laplacian eigenvalues and eigenvectors of a graph and its vertex-connectivity and edge-connectivity. \endgraf We present some new results describing the connections between the spectrum of a regular graph and other combinatorial parameters such as its generalized connectivity, toughness, and the existence of spanning trees with bounded degree. (English) |
| Keyword:
|
spectral graph theory |
| Keyword:
|
eigenvalue |
| Keyword:
|
connectivity |
| Keyword:
|
toughness |
| Keyword:
|
spanning $k$-tree |
| MSC:
|
05C05 |
| MSC:
|
05C40 |
| MSC:
|
05C42 |
| MSC:
|
05C50 |
| MSC:
|
05E99 |
| MSC:
|
15A18 |
| idZBL:
|
Zbl 06644041 |
| idMR:
|
MR3556875 |
| DOI:
|
10.1007/s10587-016-0300-z |
| . |
| Date available:
|
2016-10-01T15:36:19Z |
| Last updated:
|
2023-10-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/145879 |
| . |
| Reference:
|
[1] Alon, N.: Tough Ramsey graphs without short cycles.J. Algebr. Comb. 4 (1995), 189-195. Zbl 0826.05039, MR 1331741, 10.1023/A:1022453926717 |
| Reference:
|
[2] Bauer, D., Broersma, H. J., Schmeichel, E.: Toughness of graphs---a survey.Graphs Comb. 22 (2006), 1-35. MR 2221006, 10.1007/s00373-006-0649-0 |
| Reference:
|
[3] Bondy, J. A., Murty, U. S. R.: Graph Theory.Graduate Texts in Mathematics 244 Springer, Berlin (2008). Zbl 1134.05001, MR 2368647, 10.1007/978-1-84628-970-5_1 |
| Reference:
|
[4] Brouwer, A. E.: Spectrum and connectivity of graphs.CWI Quarterly 9 (1996), 37-40. Zbl 0872.05034, MR 1420014 |
| Reference:
|
[5] Brouwer, A. E.: Toughness and spectrum of a graph.Linear Algebra Appl. 226/228 (1995), 267-271. Zbl 0833.05048, MR 1344566 |
| Reference:
|
[6] Brouwer, A. E., Haemers, W. H.: Spectra of Graphs.Universitext Springer, Berlin (2012). Zbl 1231.05001, MR 2882891 |
| Reference:
|
[7] Butler, S., Chung, F.: Small spectral gap in the combinatorial Laplacian implies Hamiltonian.Ann. Comb. 13 (2010), 403-412. Zbl 1229.05193, MR 2581094, 10.1007/s00026-009-0039-4 |
| Reference:
|
[8] Chartrand, G., Kapoor, S. F., Lesniak, L., Lick, D. R.: Generalized connectivity in graphs.Bull. Bombay Math. Colloq. 2 (1984), 1-6. |
| Reference:
|
[9] Chvátal, V.: Tough graphs and Hamiltonian circuits.Discrete Math. 5 (1973), 215-228. Zbl 0256.05122, MR 0316301, 10.1016/0012-365X(73)90138-6 |
| Reference:
|
[10] Cioabă, S. M.: Eigenvalues and edge-connectivity of regular graphs.Linear Algebra Appl. 432 (2010), 458-470. Zbl 1211.05071, MR 2566492, 10.1016/j.laa.2009.08.029 |
| Reference:
|
[11] Cioabă, S. M., Gregory, D. A., Haemers, W. H.: Matchings in regular graphs from eigenvalues.J. Comb. Theory, Ser. B 99 (2009), 287-297. Zbl 1205.05177, MR 2482948, 10.1016/j.jctb.2008.06.008 |
| Reference:
|
[12] Cioabă, S. M., Wong, W.: The spectrum and toughness of regular graphs.Discrete Appl. Math. 176 (2014), 43-52. Zbl 1298.05200, MR 3240840, 10.1016/j.dam.2013.12.004 |
| Reference:
|
[13] Cioabă, S. M., Wong, W.: Edge-disjoint spanning trees and eigenvalues of regular graphs.Linear Algebra Appl. 437 (2012), 630-647. Zbl 1242.05056, MR 2921723, 10.1016/j.laa.2012.03.013 |
| Reference:
|
[14] Day, D. P., Oellermann, O. R., Swart, H. C.: Bounds on the size of graphs of given order and $l$-connectivity.Discrete Math. 197/198 (1999), 217-223. Zbl 0927.05051, MR 1674864 |
| Reference:
|
[15] Ellingham, M. N., Zha, X.: Toughness, trees, and walks.J. Graph Theory 33 (2000), 125-137. Zbl 0951.05068, MR 1740929, 10.1002/(SICI)1097-0118(200003)33:3<125::AID-JGT1>3.0.CO;2-X |
| Reference:
|
[16] Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory.Czech. Math. J. 25 (1975), 619-633. Zbl 0437.15004, MR 0387321, 10.21136/CMJ.1975.101357 |
| Reference:
|
[17] Fiedler, M.: Algebraic connectivity of graphs.Czech. Math. J. 23 (1973), 298-305. Zbl 0265.05119, MR 0318007, 10.21136/CMJ.1973.101168 |
| Reference:
|
[18] Godsil, C., Royle, G.: Algebraic Graph Theory.Graduate Texts in Mathematics 207 Springer, New York (2001). Zbl 0968.05002, MR 1829620 |
| Reference:
|
[19] Gu, X.: Spectral conditions for edge connectivity and packing spanning trees in multigraphs.Linear Algebra Appl. 493 (2016), 82-90. Zbl 1329.05189, MR 3452727 |
| Reference:
|
[20] Gu, X.: Regular factors and eigenvalues of regular graphs.Eur. J. Comb. 42 (2014), 15-25. Zbl 1297.05146, MR 3240134, 10.1016/j.ejc.2014.05.007 |
| Reference:
|
[21] Gu, X.: Connectivity and Spanning Trees of Graphs.PhD Dissertation, West Virginia University (2013). MR 3211328 |
| Reference:
|
[22] Gu, X., Lai, H.-J., Li, P., Yao, S.: Edge-disjoint spanning trees, edge connectivity and eigenvalues in graphs.J. Graph Theory 81 (2016), 16-29. MR 3431289, 10.1002/jgt.21857 |
| Reference:
|
[23] Gu, X., Lai, H.-J., Yao, S.: Characterization of minimally $(2,l)$-connected graphs.Inf. Process. Lett. 111 (2011), 1124-1129. Zbl 1260.05087, MR 2893946, 10.1016/j.ipl.2011.09.012 |
| Reference:
|
[24] Krivelevich, M., Sudakov, B.: Pseudo-random graphs.More Sets, Graphs and Numbers 199-262 E. Győri Bolyai Soc. Math. Stud. 15 Springer, Berlin (2006). Zbl 1098.05075, MR 2223394 |
| Reference:
|
[25] Krivelevich, M., Sudakov, B.: Sparse pseudo-random graphs are Hamiltonian.J. Graph Theory 42 (2003), 17-33. Zbl 1028.05059, MR 1943104, 10.1002/jgt.10065 |
| Reference:
|
[26] Li, G., Shi, L.: Edge-disjoint spanning trees and eigenvalues of graphs.Linear Algebra Appl. 439 (2013), 2784-2789. Zbl 1282.05128, MR 3116390, 10.1016/j.laa.2013.08.041 |
| Reference:
|
[27] Liu, B., Chen, S.: Algebraic conditions for $t$-tough graphs.Czech. Math. J. 60 (2010), 1079-1089. Zbl 1224.05307, MR 2738970, 10.1007/s10587-010-0073-8 |
| Reference:
|
[28] Liu, Q., Hong, Y., Gu, X., Lai, H.-J.: Note on edge-disjoint spanning trees and eigenvalues.Linear Algebra Appl. 458 (2014), 128-133. Zbl 1295.05146, MR 3231810 |
| Reference:
|
[29] Liu, Q., Hong, Y., Lai, H.-J.: Edge-disjoint spanning trees and eigenvalues.Linear Algebra Appl. 444 (2014), 146-151. Zbl 1295.05146, MR 3145835 |
| Reference:
|
[30] Lu, H.: Regular graphs, eigenvalues and regular factors.J. Graph Theory 69 (2012), 349-355. Zbl 1243.05153, MR 2979293, 10.1002/jgt.20581 |
| Reference:
|
[31] Lu, H.: Regular factors of regular graphs from eigenvalues.Electron. J. Comb. 17 (2010), Research paper 159, 12 pages. Zbl 1204.05057, MR 2745712 |
| Reference:
|
[32] Oellermann, O. R.: On the $l$-connectivity of a graph.Graphs Comb. 3 (1987), 285-291. MR 0903618, 10.1007/BF01788551 |
| Reference:
|
[33] Ozeki, K., Yamashita, T.: Spanning trees: A survey.Graphs Comb. 27 (2011), 1-26. Zbl 1232.05055, MR 2746831, 10.1007/s00373-010-0973-2 |
| Reference:
|
[34] Win, S.: On a connection between the existence of $k$-trees and the toughness of a graph.Graphs Comb. 5 (1989), 201-205. Zbl 0673.05054, MR 0998275, 10.1007/BF01788671 |
| Reference:
|
[35] Wong, W.: Spanning Trees, Toughness, and Eigenvalues of Regular Graphs.PhD Dissertation, University of Delaware (2013), available at http://pqdtopen.proquest.com/doc/1443835286.html?FMT=ABS. MR 3192853 |
| . |
