Article
MSC:
05C05,
05C40,
05C42,
05C50,
05E99,
15A18 | MR 3556875 | Zbl 06644041 | DOI: 10.1007/s10587-016-0300-z
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
spectral graph theory; eigenvalue; connectivity; toughness; spanning $k$-tree
spectral graph theory; eigenvalue; connectivity; toughness; spanning $k$-tree
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.
References:
[1] Alon, N.: Tough Ramsey graphs without short cycles. J. Algebr. Comb. 4 (1995), 189-195. DOI 10.1023/A:1022453926717 | MR 1331741 | Zbl 0826.05039
[2] Bauer, D., Broersma, H. J., Schmeichel, E.: Toughness of graphs---a survey. Graphs Comb. 22 (2006), 1-35. DOI 10.1007/s00373-006-0649-0 | MR 2221006
[3] Bondy, J. A., Murty, U. S. R.: Graph Theory. Graduate Texts in Mathematics 244 Springer, Berlin (2008). DOI 10.1007/978-1-84628-970-5_1 | MR 2368647 | Zbl 1134.05001
[4] Brouwer, A. E.: Spectrum and connectivity of graphs. CWI Quarterly 9 (1996), 37-40. MR 1420014 | Zbl 0872.05034
[5] Brouwer, A. E.: Toughness and spectrum of a graph. Linear Algebra Appl. 226/228 (1995), 267-271. MR 1344566 | Zbl 0833.05048
[6] Brouwer, A. E., Haemers, W. H.: Spectra of Graphs. Universitext Springer, Berlin (2012). MR 2882891 | Zbl 1231.05001
[7] Butler, S., Chung, F.: Small spectral gap in the combinatorial Laplacian implies Hamiltonian. Ann. Comb. 13 (2010), 403-412. DOI 10.1007/s00026-009-0039-4 | MR 2581094 | Zbl 1229.05193
[8] Chartrand, G., Kapoor, S. F., Lesniak, L., Lick, D. R.: Generalized connectivity in graphs. Bull. Bombay Math. Colloq. 2 (1984), 1-6.
[9] Chvátal, V.: Tough graphs and Hamiltonian circuits. Discrete Math. 5 (1973), 215-228. DOI 10.1016/0012-365X(73)90138-6 | MR 0316301 | Zbl 0256.05122
[10] Cioabă, S. M.: Eigenvalues and edge-connectivity of regular graphs. Linear Algebra Appl. 432 (2010), 458-470. DOI 10.1016/j.laa.2009.08.029 | MR 2566492 | Zbl 1211.05071
[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. DOI 10.1016/j.jctb.2008.06.008 | MR 2482948 | Zbl 1205.05177
[12] Cioabă, S. M., Wong, W.: The spectrum and toughness of regular graphs. Discrete Appl. Math. 176 (2014), 43-52. DOI 10.1016/j.dam.2013.12.004 | MR 3240840 | Zbl 1298.05200
[13] Cioabă, S. M., Wong, W.: Edge-disjoint spanning trees and eigenvalues of regular graphs. Linear Algebra Appl. 437 (2012), 630-647. DOI 10.1016/j.laa.2012.03.013 | MR 2921723 | Zbl 1242.05056
[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. MR 1674864 | Zbl 0927.05051
[15] Ellingham, M. N., Zha, X.: Toughness, trees, and walks. J. Graph Theory 33 (2000), 125-137. DOI 10.1002/(SICI)1097-0118(200003)33:3<125::AID-JGT1>3.0.CO;2-X | MR 1740929 | Zbl 0951.05068
[16] Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech. Math. J. 25 (1975), 619-633. DOI 10.21136/CMJ.1975.101357 | MR 0387321 | Zbl 0437.15004
[17] Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298-305. DOI 10.21136/CMJ.1973.101168 | MR 0318007 | Zbl 0265.05119
[18] Godsil, C., Royle, G.: Algebraic Graph Theory. Graduate Texts in Mathematics 207 Springer, New York (2001). MR 1829620 | Zbl 0968.05002
[19] Gu, X.: Spectral conditions for edge connectivity and packing spanning trees in multigraphs. Linear Algebra Appl. 493 (2016), 82-90. MR 3452727 | Zbl 1329.05189
[20] Gu, X.: Regular factors and eigenvalues of regular graphs. Eur. J. Comb. 42 (2014), 15-25. DOI 10.1016/j.ejc.2014.05.007 | MR 3240134 | Zbl 1297.05146
[21] Gu, X.: Connectivity and Spanning Trees of Graphs. PhD Dissertation, West Virginia University (2013). MR 3211328
[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. DOI 10.1002/jgt.21857 | MR 3431289
[23] Gu, X., Lai, H.-J., Yao, S.: Characterization of minimally $(2,l)$-connected graphs. Inf. Process. Lett. 111 (2011), 1124-1129. DOI 10.1016/j.ipl.2011.09.012 | MR 2893946 | Zbl 1260.05087
[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). MR 2223394 | Zbl 1098.05075
[25] Krivelevich, M., Sudakov, B.: Sparse pseudo-random graphs are Hamiltonian. J. Graph Theory 42 (2003), 17-33. DOI 10.1002/jgt.10065 | MR 1943104 | Zbl 1028.05059
[26] Li, G., Shi, L.: Edge-disjoint spanning trees and eigenvalues of graphs. Linear Algebra Appl. 439 (2013), 2784-2789. DOI 10.1016/j.laa.2013.08.041 | MR 3116390 | Zbl 1282.05128
[27] Liu, B., Chen, S.: Algebraic conditions for $t$-tough graphs. Czech. Math. J. 60 (2010), 1079-1089. DOI 10.1007/s10587-010-0073-8 | MR 2738970 | Zbl 1224.05307
[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. MR 3231810 | Zbl 1295.05146
[29] Liu, Q., Hong, Y., Lai, H.-J.: Edge-disjoint spanning trees and eigenvalues. Linear Algebra Appl. 444 (2014), 146-151. MR 3145835 | Zbl 1295.05146
[30] Lu, H.: Regular graphs, eigenvalues and regular factors. J. Graph Theory 69 (2012), 349-355. DOI 10.1002/jgt.20581 | MR 2979293 | Zbl 1243.05153
[31] Lu, H.: Regular factors of regular graphs from eigenvalues. Electron. J. Comb. 17 (2010), Research paper 159, 12 pages. MR 2745712 | Zbl 1204.05057
[32] Oellermann, O. R.: On the $l$-connectivity of a graph. Graphs Comb. 3 (1987), 285-291. DOI 10.1007/BF01788551 | MR 0903618
[33] Ozeki, K., Yamashita, T.: Spanning trees: A survey. Graphs Comb. 27 (2011), 1-26. DOI 10.1007/s00373-010-0973-2 | MR 2746831 | Zbl 1232.05055
[34] Win, S.: On a connection between the existence of $k$-trees and the toughness of a graph. Graphs Comb. 5 (1989), 201-205. DOI 10.1007/BF01788671 | MR 0998275 | Zbl 0673.05054
[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
Search
Partner of
