Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs

Sebastian M. Cioabă; Xiaofeng Gu

Czechoslovak Mathematical Journal (2016)

  • Volume: 66, Issue: 3, page 913-924
  • ISSN: 0011-4642

Abstract

top
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. 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.

How to cite

top

Cioabă, Sebastian M., and Gu, Xiaofeng. "Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs." Czechoslovak Mathematical Journal 66.3 (2016): 913-924. <http://eudml.org/doc/286790>.

@article{Cioabă2016,
abstract = {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. 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.},
author = {Cioabă, Sebastian M., Gu, Xiaofeng},
journal = {Czechoslovak Mathematical Journal},
keywords = {spectral graph theory; eigenvalue; connectivity; toughness; spanning $k$-tree},
language = {eng},
number = {3},
pages = {913-924},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs},
url = {http://eudml.org/doc/286790},
volume = {66},
year = {2016},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 66
IS - 3
SP - 913
EP - 924
AB - 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. 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.
LA - eng
KW - spectral graph theory; eigenvalue; connectivity; toughness; spanning $k$-tree
UR - http://eudml.org/doc/286790
ER -

References

top
  1. Alon, N., 10.1023/A:1022453926717, J. Algebr. Comb. 4 (1995), 189-195. (1995) Zbl0826.05039MR1331741DOI10.1023/A:1022453926717
  2. Bauer, D., Broersma, H. J., Schmeichel, E., 10.1007/s00373-006-0649-0, Graphs Comb. 22 (2006), 1-35. (2006) MR2221006DOI10.1007/s00373-006-0649-0
  3. Bondy, J. A., Murty, U. S. R., 10.1007/978-1-84628-970-5_1, Graduate Texts in Mathematics 244 Springer, Berlin (2008). (2008) Zbl1134.05001MR2368647DOI10.1007/978-1-84628-970-5_1
  4. Brouwer, A. E., Spectrum and connectivity of graphs, CWI Quarterly 9 (1996), 37-40. (1996) Zbl0872.05034MR1420014
  5. Brouwer, A. E., Toughness and spectrum of a graph, Linear Algebra Appl. 226/228 (1995), 267-271. (1995) Zbl0833.05048MR1344566
  6. Brouwer, A. E., Haemers, W. H., Spectra of Graphs, Universitext Springer, Berlin (2012). (2012) Zbl1231.05001MR2882891
  7. Butler, S., Chung, F., 10.1007/s00026-009-0039-4, Ann. Comb. 13 (2010), 403-412. (2010) Zbl1229.05193MR2581094DOI10.1007/s00026-009-0039-4
  8. Chartrand, G., Kapoor, S. F., Lesniak, L., Lick, D. R., Generalized connectivity in graphs, Bull. Bombay Math. Colloq. 2 (1984), 1-6. (1984) 
  9. Chvátal, V., 10.1016/0012-365X(73)90138-6, Discrete Math. 5 (1973), 215-228. (1973) Zbl0256.05122MR0316301DOI10.1016/0012-365X(73)90138-6
  10. Cioabă, S. M., 10.1016/j.laa.2009.08.029, Linear Algebra Appl. 432 (2010), 458-470. (2010) Zbl1211.05071MR2566492DOI10.1016/j.laa.2009.08.029
  11. Cioabă, S. M., Gregory, D. A., Haemers, W. H., 10.1016/j.jctb.2008.06.008, J. Comb. Theory, Ser. B 99 (2009), 287-297. (2009) Zbl1205.05177MR2482948DOI10.1016/j.jctb.2008.06.008
  12. Cioabă, S. M., Wong, W., 10.1016/j.dam.2013.12.004, Discrete Appl. Math. 176 (2014), 43-52. (2014) Zbl1298.05200MR3240840DOI10.1016/j.dam.2013.12.004
  13. Cioabă, S. M., Wong, W., 10.1016/j.laa.2012.03.013, Linear Algebra Appl. 437 (2012), 630-647. (2012) Zbl1242.05056MR2921723DOI10.1016/j.laa.2012.03.013
  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. (1999) Zbl0927.05051MR1674864
  15. Ellingham, M. N., Zha, X., 10.1002/(SICI)1097-0118(200003)33:3<125::AID-JGT1>3.0.CO;2-X, J. Graph Theory 33 (2000), 125-137. (2000) Zbl0951.05068MR1740929DOI10.1002/(SICI)1097-0118(200003)33:3<125::AID-JGT1>3.0.CO;2-X
  16. Fiedler, M., A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czech. Math. J. 25 (1975), 619-633. (1975) Zbl0437.15004MR0387321
  17. Fiedler, M., Algebraic connectivity of graphs, Czech. Math. J. 23 (1973), 298-305. (1973) Zbl0265.05119MR0318007
  18. Godsil, C., Royle, G., Algebraic Graph Theory, Graduate Texts in Mathematics 207 Springer, New York (2001). (2001) Zbl0968.05002MR1829620
  19. Gu, X., Spectral conditions for edge connectivity and packing spanning trees in multigraphs, Linear Algebra Appl. 493 (2016), 82-90. (2016) Zbl1329.05189MR3452727
  20. Gu, X., 10.1016/j.ejc.2014.05.007, Eur. J. Comb. 42 (2014), 15-25. (2014) Zbl1297.05146MR3240134DOI10.1016/j.ejc.2014.05.007
  21. Gu, X., Connectivity and Spanning Trees of Graphs, PhD Dissertation, West Virginia University (2013). (2013) MR3211328
  22. Gu, X., Lai, H.-J., Li, P., Yao, S., 10.1002/jgt.21857, J. Graph Theory 81 (2016), 16-29. (2016) MR3431289DOI10.1002/jgt.21857
  23. Gu, X., Lai, H.-J., Yao, S., 10.1016/j.ipl.2011.09.012, Inf. Process. Lett. 111 (2011), 1124-1129. (2011) Zbl1260.05087MR2893946DOI10.1016/j.ipl.2011.09.012
  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). (2006) Zbl1098.05075MR2223394
  25. Krivelevich, M., Sudakov, B., 10.1002/jgt.10065, J. Graph Theory 42 (2003), 17-33. (2003) Zbl1028.05059MR1943104DOI10.1002/jgt.10065
  26. Li, G., Shi, L., 10.1016/j.laa.2013.08.041, Linear Algebra Appl. 439 (2013), 2784-2789. (2013) Zbl1282.05128MR3116390DOI10.1016/j.laa.2013.08.041
  27. Liu, B., Chen, S., 10.1007/s10587-010-0073-8, Czech. Math. J. 60 (2010), 1079-1089. (2010) Zbl1224.05307MR2738970DOI10.1007/s10587-010-0073-8
  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. (2014) Zbl1295.05146MR3231810
  29. Liu, Q., Hong, Y., Lai, H.-J., Edge-disjoint spanning trees and eigenvalues, Linear Algebra Appl. 444 (2014), 146-151. (2014) Zbl1295.05146MR3145835
  30. Lu, H., 10.1002/jgt.20581, J. Graph Theory 69 (2012), 349-355. (2012) Zbl1243.05153MR2979293DOI10.1002/jgt.20581
  31. Lu, H., Regular factors of regular graphs from eigenvalues, Electron. J. Comb. 17 (2010), Research paper 159, 12 pages. (2010) Zbl1204.05057MR2745712
  32. Oellermann, O. R., 10.1007/BF01788551, Graphs Comb. 3 (1987), 285-291. (1987) MR0903618DOI10.1007/BF01788551
  33. Ozeki, K., Yamashita, T., 10.1007/s00373-010-0973-2, Graphs Comb. 27 (2011), 1-26. (2011) Zbl1232.05055MR2746831DOI10.1007/s00373-010-0973-2
  34. Win, S., 10.1007/BF01788671, Graphs Comb. 5 (1989), 201-205. (1989) Zbl0673.05054MR0998275DOI10.1007/BF01788671
  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. (2013) MR3192853

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.