On graphs whose Laplacian matrices have distinct integer eigenvalues

Abstract

Abstract 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