Premium
On graphs whose Laplacian matrices have distinct integer eigenvalues
Author(s) -
Fallat Shaun M.,
Kirkland Stephen J.,
Molitierno Jason J.,
Neumann M.
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20102
Subject(s) - laplacian matrix , mathematics , conjecture , eigenvalues and eigenvectors , combinatorics , laplace operator , resistance distance , algebraic connectivity , graph , discrete mathematics , integer (computer science) , set (abstract data type) , matrix (chemical analysis) , line graph , graph power , computer science , mathematical analysis , physics , materials science , quantum mechanics , composite material , programming language
In this paper, we investigate graphs for which the corresponding Laplacian matrix has distinct integer eigenvalues. We define the set S i,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 S i,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 S i,n is Laplacian realizable, and show that for certain values of i , the set S i,n is realized by a unique graph. Finally, we conjecture that S n,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 Theory