Elsevier, Linear Algebra and its Applications, 4(438), p. 1541-1550, 2013
DOI: 10.1016/j.laa.2011.02.043
Full text: Download
Let A(G) and D(G) be the adjacency matrix and the vertex degree matrix of a graph G, respectively. The Laplacian matrix of G is defined as L(G)=D(G)−A(G). The L-index of G, denoted by μ(G), is the largest root of the characteristic polynomial of L(G). The Laplacian Hoffman limit value H(L) is the limit of μ(Hn), where the graph Hn is obtained by attaching a pendant edge to the cycle Cn-1 of length n-1. It is known that H(L)=2+ϵ, where ϵ is the largest root of x3-4x-4. In this paper we characterize the structure of graphs whose L-index does not exceed 4.5, and we completely describe those graphs whose L-index does not exceed H(L). By doing so we complete the so-called Hoffman program w.r.t. the Laplacian theory of graph spectra.