Geodesic
Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs
Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 913-924
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.1007/s10587-016-0300-z
Classification : 05C05, 05C40, 05C42, 05C50, 05E99, 15A18
Keywords: spectral graph theory; eigenvalue; connectivity; toughness; spanning $k$-tree 
@article{10_1007_s10587_016_0300_z,
     author = {Cioab\u{a}, Sebastian M. and Gu, Xiaofeng},
     title = {Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {913--924},
     year = {2016},
     volume = {66},
     number = {3},
     doi = {10.1007/s10587-016-0300-z},
     mrnumber = {3556875},
     zbl = {06644041},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0300-z/}
}
TY  - JOUR
AU  - Cioabă, Sebastian M.
AU  - Gu, Xiaofeng
TI  - Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2016
SP  - 913
EP  - 924
VL  - 66
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0300-z/
DO  - 10.1007/s10587-016-0300-z
LA  - en
ID  - 10_1007_s10587_016_0300_z
ER  - 
%0 Journal Article
%A Cioabă, Sebastian M.
%A Gu, Xiaofeng
%T Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs
%J Czechoslovak Mathematical Journal
%D 2016
%P 913-924
%V 66
%N 3
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0300-z/
%R 10.1007/s10587-016-0300-z
%G en
%F 10_1007_s10587_016_0300_z
Cioabă, Sebastian M.; Gu, Xiaofeng. Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs. Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 913-924. doi: 10.1007/s10587-016-0300-z

[1] Alon, N.: Tough Ramsey graphs without short cycles. J. Algebr. Comb. 4 (1995), 189-195. | DOI | MR | Zbl

[2] Bauer, D., Broersma, H. J., Schmeichel, E.: Toughness of graphs---a survey. Graphs Comb. 22 (2006), 1-35. | DOI | MR

[3] Bondy, J. A., Murty, U. S. R.: Graph Theory. Graduate Texts in Mathematics 244 Springer, Berlin (2008). | DOI | MR | Zbl

[4] Brouwer, A. E.: Spectrum and connectivity of graphs. CWI Quarterly 9 (1996), 37-40. | MR | Zbl

[5] Brouwer, A. E.: Toughness and spectrum of a graph. Linear Algebra Appl. 226/228 (1995), 267-271. | MR | Zbl

[6] Brouwer, A. E., Haemers, W. H.: Spectra of Graphs. Universitext Springer, Berlin (2012). | MR | Zbl

[7] Butler, S., Chung, F.: Small spectral gap in the combinatorial Laplacian implies Hamiltonian. Ann. Comb. 13 (2010), 403-412. | DOI | MR | Zbl

[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 | MR | Zbl

[10] Cioabă, S. M.: Eigenvalues and edge-connectivity of regular graphs. Linear Algebra Appl. 432 (2010), 458-470. | DOI | MR | Zbl

[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 | MR | Zbl

[12] Cioabă, S. M., Wong, W.: The spectrum and toughness of regular graphs. Discrete Appl. Math. 176 (2014), 43-52. | DOI | MR | Zbl

[13] Cioabă, S. M., Wong, W.: Edge-disjoint spanning trees and eigenvalues of regular graphs. Linear Algebra Appl. 437 (2012), 630-647. | DOI | MR | Zbl

[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 | Zbl

[15] Ellingham, M. N., Zha, X.: Toughness, trees, and walks. J. Graph Theory 33 (2000), 125-137. | DOI | MR | Zbl

[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 | MR | Zbl

[17] Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298-305. | DOI | MR | Zbl

[18] Godsil, C., Royle, G.: Algebraic Graph Theory. Graduate Texts in Mathematics 207 Springer, New York (2001). | MR | Zbl

[19] Gu, X.: Spectral conditions for edge connectivity and packing spanning trees in multigraphs. Linear Algebra Appl. 493 (2016), 82-90. | MR | Zbl

[20] Gu, X.: Regular factors and eigenvalues of regular graphs. Eur. J. Comb. 42 (2014), 15-25. | DOI | MR | Zbl

[21] Gu, X.: Connectivity and Spanning Trees of Graphs. PhD Dissertation, West Virginia University (2013). | MR

[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 | MR

[23] Gu, X., Lai, H.-J., Yao, S.: Characterization of minimally $(2,l)$-connected graphs. Inf. Process. Lett. 111 (2011), 1124-1129. | DOI | MR | Zbl

[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 | Zbl

[25] Krivelevich, M., Sudakov, B.: Sparse pseudo-random graphs are Hamiltonian. J. Graph Theory 42 (2003), 17-33. | DOI | MR | Zbl

[26] Li, G., Shi, L.: Edge-disjoint spanning trees and eigenvalues of graphs. Linear Algebra Appl. 439 (2013), 2784-2789. | DOI | MR | Zbl

[27] Liu, B., Chen, S.: Algebraic conditions for $t$-tough graphs. Czech. Math. J. 60 (2010), 1079-1089. | DOI | MR | Zbl

[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 | Zbl

[29] Liu, Q., Hong, Y., Lai, H.-J.: Edge-disjoint spanning trees and eigenvalues. Linear Algebra Appl. 444 (2014), 146-151. | MR | Zbl

[30] Lu, H.: Regular graphs, eigenvalues and regular factors. J. Graph Theory 69 (2012), 349-355. | DOI | MR | Zbl

[31] Lu, H.: Regular factors of regular graphs from eigenvalues. Electron. J. Comb. 17 (2010), Research paper 159, 12 pages. | MR | Zbl

[32] Oellermann, O. R.: On the $l$-connectivity of a graph. Graphs Comb. 3 (1987), 285-291. | DOI | MR

[33] Ozeki, K., Yamashita, T.: Spanning trees: A survey. Graphs Comb. 27 (2011), 1-26. | DOI | MR | Zbl

[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 | MR | Zbl

[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

Cité par Sources :