On the conjecture for certain Laplacian integral spectrum of graphs

✍ Scribed by Kinkar Ch. Das; Sang-Gu Lee; Gi-Sang Cheon

• Publisher: John Wiley and Sons
• Year: 2009
• Tongue: English
• Weight: 184 KB
• Volume: 63
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20412

✦ Synopsis

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