Premium
On the conjecture for certain Laplacian integral spectrum of graphs
Author(s) -
Das Kinkar Ch.,
Lee SangGu,
Cheon GiSang
Publication year - 2010
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.20412
Subject(s) - mathematics , conjecture , combinatorics , laplace operator , spectrum (functional analysis) , graph , complement (music) , order (exchange) , discrete mathematics , simple graph , mathematical analysis , physics , biochemistry , chemistry , finance , quantum mechanics , complementation , economics , gene , phenotype
Abstract 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