On graphs whose Laplacian matrices have distinct integer eigenvalues
- 3 June 2005
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 50 (2) , 162-174
Abstract
In this paper, we investigate graphs for which the corresponding Laplacian matrix has distinct integer eigenvalues. We define the set Si,n to be the set of all integers from 0 to n, excluding i. If there exists a graph whose Laplacian matrix has this set as its eigenvalues, we say that this set is Laplacian realizable. We investigate the sets Si,n that are Laplacian realizable, and the structures of the graphs whose Laplacian matrix has such a set as its eigenvalues. We characterize those i < n such that Si,n is Laplacian realizable, and show that for certain values of i, the set Si,n is realized by a unique graph. Finally, we conjecture that Sn,n is not Laplacian realizable for n ≥ 2 and show that the conjecture holds for certain values of n. © 2005 Wiley Periodicals, Inc. J Graph TheoryKeywords
This publication has 8 references indexed in Scilit:
- On graphs with equal algebraic and vertex connectivityLinear Algebra and its Applications, 2002
- A Course in Combinatorics2001
- Algebraic Graph Theory2001
- Laplacian graph eigenvectorsLinear Algebra and its Applications, 1998
- The Laplacian Spectrum of a Graph IISIAM Journal on Discrete Mathematics, 1994
- Laplacian matrices of graphs: a surveyLinear Algebra and its Applications, 1994
- Large eigenvalues of the laplacianLinear and Multilinear Algebra, 1990
- Algebraic connectivity of graphsCzechoslovak Mathematical Journal, 1973