On the conjecture for certain Laplacian integral spectrum of graphs

Let G be a simple graph of order n with Laplacian spectrum {λ n , λ n −1 , …, λ 1 } where 0=λ n ≤λ n −1 ≤⋅≤λ 1 . If there exists a graph whose Laplacian spectrum is S ={0, 1, …, n −1}, then we say that S is Laplacian realizable. In 6, Fallat et al. posed a conjecture that S is not Laplacian realizable for any n ≥2 and showed that the conjecture holds for n ≤11, n is prime, or n =2, 3(mod4). In this article, we have proved that (i) if G is connected and λ 1 = n −1 then G has diameter either 2 or 3, and (ii) if λ 1 = n −1 and λ n −1 =1 then both G and Ḡ, the complement of G , have diameter 3. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 106–113, 2010