On spectral characterizations and embeddings of graphs

AbstractThe least eigenvalue of the 0-1 adjacency matrix of a graph is denoted λ G. In this paper all graphs with λ(G) greater than −2 are characterized. Such a graph is a generalized line graph of the form L(T;1,0,…,0), L(T), L(H), where T is a tree and H is unicyclic with an odd cycle, or is one of 573 graphs that arise from the root system E8. If G is regular with λ(G)>−2, then Gis a clique or an odd circuit. These characterizations are used for embedding problems; λR(H) = sup{λ(G)z.sfnc;H in G; G regular}. H is an odd circuit, a path, or a complete graph iff λR(H)> −2. For any other line graph H, λR(H) = −2. A similar result holds for complete multipartite graphs