Graphs with four distinct Laplacian eigenvalues

Journal of Algebraic Combinatorics - Tập 34 Số 4 - Trang 671-682 - 2011
Mohammadian, A.1, Tayfeh-Rezaie, B.1
1School of Mathematics, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran

Tóm tắt

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.

Từ khóa


Tài liệu tham khảo

citation_journal_title=Aequ. Math.; citation_title=Multiplicative cones—a family of three eigenvalue graphs; citation_author=W.G. Bridges, R.A. Mena; citation_volume=22; citation_publication_date=1981; citation_pages=208-214; citation_doi=10.1007/BF02190180; citation_id=CR1

citation_journal_title=Linear Algebra Appl.; citation_title=A lower bound for the Laplacian eigenvalues of a graph—proof of a conjecture by Guo; citation_author=A.E. Brouwer, W.H. Haemers; citation_volume=429; citation_publication_date=2008; citation_pages=2131-2135; citation_doi=10.1016/j.laa.2008.06.008; citation_id=CR2

citation_journal_title=J. Comb. Theory, Ser. A; citation_title=A nonregular analogue of conference graphs; citation_author=D. Caen, E.R. Dam, E. Spence; citation_volume=88; citation_publication_date=1999; citation_pages=194-204; citation_doi=10.1006/jcta.1999.2983; citation_id=CR3

citation_title=Spectra of Graphs: Theory and Application; citation_publication_date=1979; citation_id=CR4; citation_author=D.M. Cvetković; citation_author=M. Doob; citation_author=H. Sachs; citation_publisher=V.E.B. Deutscher Verlag der Wissenschaften

citation_journal_title=J. Comb. Theory, Ser. B; citation_title=Nonregular graphs with three eigenvalues; citation_author=E.R. Dam; citation_volume=73; citation_publication_date=1998; citation_pages=101-118; citation_doi=10.1006/jctb.1998.1815; citation_id=CR5

citation_journal_title=Linear Algebra Appl.; citation_title=Regular graphs with four eigenvalues; citation_author=E.R. Dam; citation_volume=226/228; citation_publication_date=1995; citation_pages=139-162; citation_doi=10.1016/0024-3795(94)00346-F; citation_id=CR6

citation_journal_title=Discrete Math.; citation_title=Graphs with constant μ and ; citation_author=E.R. Dam, W.H. Haemers; citation_volume=182; citation_publication_date=1998; citation_pages=293-307; citation_doi=10.1016/S0012-365X(97)00150-7; citation_id=CR7

citation_journal_title=Linear Algebra Appl.; citation_title=Combinatorial designs with two singular values II. Partial geometric designs; citation_author=E.R. Dam, E. Spence; citation_volume=396; citation_publication_date=2005; citation_pages=303-316; citation_doi=10.1016/j.laa.2004.09.015; citation_id=CR8

citation_journal_title=J. Comb. Theory, Ser. A; citation_title=Combinatorial designs with two singular values I: uniform multiplicative designs; citation_author=E.R. Dam, E. Spence; citation_volume=107; citation_publication_date=2004; citation_pages=127-142; citation_doi=10.1016/j.jcta.2004.04.004; citation_id=CR9

citation_journal_title=Discrete Math.; citation_title=Small regular graphs with four eigenvalues; citation_author=E.R. Dam, E. Spence; citation_volume=189; citation_publication_date=1998; citation_pages=233-257; citation_doi=10.1016/S0012-365X(98)00085-5; citation_id=CR10

citation_journal_title=Graphs Comb.; citation_title=A sharp upper bound for the number of spanning trees of a graph; citation_author=K.C. Das; citation_volume=23; citation_publication_date=2007; citation_pages=625-632; citation_doi=10.1007/s00373-007-0758-4; citation_id=CR11

citation_journal_title=Linear Algebra Appl.; citation_title=An improved upper bound for Laplacian graph eigenvalues; citation_author=K.C. Das; citation_volume=368; citation_publication_date=2003; citation_pages=269-278; citation_doi=10.1016/S0024-3795(02)00687-0; citation_id=CR12

citation_title=Algebraic Graph Theory; citation_publication_date=2001; citation_id=CR13; citation_author=C. Godsil; citation_author=G. Royle; citation_publisher=Springer

citation_journal_title=Linear Algebra Appl.; citation_title=On graphs with equal algebraic and vertex connectivity; citation_author=S.J. Kirkland, J.J. Molitierno, M. Neumann, B.L. Shader; citation_volume=341; citation_publication_date=2002; citation_pages=45-56; citation_doi=10.1016/S0024-3795(01)00312-3; citation_id=CR14

citation_journal_title=Linear Algebra Appl.; citation_title=Laplacian graph eigenvectors; citation_author=R. Merris; citation_volume=278; citation_publication_date=1998; citation_pages=221-236; citation_doi=10.1016/S0024-3795(97)10080-5; citation_id=CR15

citation_journal_title=Discrete Math.; citation_title=On graphs with three eigenvalues; citation_author=M. Muzychuk, M. Klin; citation_volume=189; citation_publication_date=1998; citation_pages=191-207; citation_doi=10.1016/S0012-365X(98)00084-3; citation_id=CR16

citation_journal_title=Appl. Math. J. Chin. Univ. Ser. B; citation_title=On graphs with three distinct Laplacian eigenvalues; citation_author=Y. Wang, Y. Fan, Y. Tan; citation_volume=22; citation_publication_date=2007; citation_pages=478-484; citation_doi=10.1007/s11766-007-0414-z; citation_id=CR17