Graphs with four distinct Laplacian eigenvalues
A. Mohammadian
and B. Tayfeh-Rezaie2
2A. Mohammadian
DOI: 10.1007/s10801-011-0287-3
Abstract
In this paper, we investigate connected nonregular graphs with four distinct Laplacian eigenvalues. We characterize all such graphs which are bipartite or have exactly one multiple Laplacian eigenvalue. Other examples of interest are also presented.
Pages: 671–682
Keywords: keywords Laplacian eigenvalue; bipartite graph; multiple eigenvalue
Full Text: PDF
References
1. Bridges, W.G., Mena, R.A.: Multiplicative cones-a family of three eigenvalue graphs. Aequ. Math. 22, 208-214 (1981)
2. Brouwer, A.E., Haemers, W.H.: A lower bound for the Laplacian eigenvalues of a graph-proof of a conjecture by Guo. Linear Algebra Appl. 429, 2131-2135 (2008) 3. de Caen, D., van Dam, E.R., Spence, E.: A nonregular analogue of conference graphs. J. Comb. Theory, Ser. A 88, 194-204 (1999)
4. Cvetković, D.M., Doob, M., Sachs, H.: Spectra of Graphs: Theory and Application. V.E.B. Deutscher Verlag der Wissenschaften, Berlin (1979) 5. van Dam, E.R.: Nonregular graphs with three eigenvalues. J. Comb. Theory, Ser. B 73, 101-118 (1998) J Algebr Comb (2011) 34:671-682 6. van Dam, E.R.: Regular graphs with four eigenvalues. Linear Algebra Appl. 226/228, 139-162 (1995) 7. van Dam, E.R., Haemers, W.H.: Graphs with constant μand μ. Discrete Math. 182, 293-307 (1998) 8. van Dam, E.R., Spence, E.: Combinatorial designs with two singular values II. Partial geometric designs. Linear Algebra Appl. 396, 303-316 (2005) 9. van Dam, E.R., Spence, E.: Combinatorial designs with two singular values I: uniform multiplicative designs. J. Comb. Theory, Ser. A 107, 127-142 (2004) 10. van Dam, E.R., Spence, E.: Small regular graphs with four eigenvalues. Discrete Math. 189, 233-257 (1998)
11. Das, K.C.: A sharp upper bound for the number of spanning trees of a graph. Graphs Comb. 23, 625-632 (2007)
12. Das, K.C.: An improved upper bound for Laplacian graph eigenvalues. Linear Algebra Appl. 368, 269-278 (2003)
13. Godsil, C., Royle, G.: Algebraic Graph Theory. Springer, New York (2001)
14. Kirkland, S.J., Molitierno, J.J., Neumann, M., Shader, B.L.: On graphs with equal algebraic and vertex connectivity. Linear Algebra Appl. 341, 45-56 (2002)
15. Merris, R.: Laplacian graph eigenvectors. Linear Algebra Appl. 278, 221-236 (1998)
16. Muzychuk, M., Klin, M.: On graphs with three eigenvalues. Discrete Math. 189, 191-207 (1998)
17. Wang, Y., Fan, Y., Tan, Y.: On graphs with three distinct Laplacian eigenvalues. Appl. Math. J. Chin.
2. Brouwer, A.E., Haemers, W.H.: A lower bound for the Laplacian eigenvalues of a graph-proof of a conjecture by Guo. Linear Algebra Appl. 429, 2131-2135 (2008) 3. de Caen, D., van Dam, E.R., Spence, E.: A nonregular analogue of conference graphs. J. Comb. Theory, Ser. A 88, 194-204 (1999)
4. Cvetković, D.M., Doob, M., Sachs, H.: Spectra of Graphs: Theory and Application. V.E.B. Deutscher Verlag der Wissenschaften, Berlin (1979) 5. van Dam, E.R.: Nonregular graphs with three eigenvalues. J. Comb. Theory, Ser. B 73, 101-118 (1998) J Algebr Comb (2011) 34:671-682 6. van Dam, E.R.: Regular graphs with four eigenvalues. Linear Algebra Appl. 226/228, 139-162 (1995) 7. van Dam, E.R., Haemers, W.H.: Graphs with constant μand μ. Discrete Math. 182, 293-307 (1998) 8. van Dam, E.R., Spence, E.: Combinatorial designs with two singular values II. Partial geometric designs. Linear Algebra Appl. 396, 303-316 (2005) 9. van Dam, E.R., Spence, E.: Combinatorial designs with two singular values I: uniform multiplicative designs. J. Comb. Theory, Ser. A 107, 127-142 (2004) 10. van Dam, E.R., Spence, E.: Small regular graphs with four eigenvalues. Discrete Math. 189, 233-257 (1998)
11. Das, K.C.: A sharp upper bound for the number of spanning trees of a graph. Graphs Comb. 23, 625-632 (2007)
12. Das, K.C.: An improved upper bound for Laplacian graph eigenvalues. Linear Algebra Appl. 368, 269-278 (2003)
13. Godsil, C., Royle, G.: Algebraic Graph Theory. Springer, New York (2001)
14. Kirkland, S.J., Molitierno, J.J., Neumann, M., Shader, B.L.: On graphs with equal algebraic and vertex connectivity. Linear Algebra Appl. 341, 45-56 (2002)
15. Merris, R.: Laplacian graph eigenvectors. Linear Algebra Appl. 278, 221-236 (1998)
16. Muzychuk, M., Klin, M.: On graphs with three eigenvalues. Discrete Math. 189, 191-207 (1998)
17. Wang, Y., Fan, Y., Tan, Y.: On graphs with three distinct Laplacian eigenvalues. Appl. Math. J. Chin.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition