Graphs with least eigenvalue -2: The star complement technique

DOI10.1023/A:1011209801191MaRDI QIDQ5949011zbMATH OpenOpenAlexFDO

Authors Dragoš Cvetković, P. Rowlinson, Slobodan K. Simić

Publication date 29 March 2002

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1011209801191

eigenspace eigenvalue exceptional graphs graph

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75)

Review text

If a connected graph has \(-2\) as its least eigenvalue, then it is either a generalized line graph or a graph representable in the root system \(E_8\) (which is proved in \textit{R. I. Cameron} et al. [J. Algebra 43, 305-327 (1976; Zbl 0337.05142)]). The connected graphs which have least eigenvalue greater than or equal to \(-2\), and which are not generalized line graphs, are called exceptional. Search for exceptional graphs lasted for some 30 years and nowadays it is known that there are 573 of them. Some further details on exceptional graphs can be found in \textit{F. C. Bussemaker} and \textit{A. Neumaier} [Math. Comput. 59, 583-608 (1992; Zbl 0770.05060)]. Let \(G\) be a simple graph with eigenvalue \(\mu\) of its adjacency matrix. If \(\mu\) has multiplicity \(k\) then a star set for \(\mu\) is a set \(X\) of \(k\) vertices of \(G\) such that \(\mu\) is not an eigenvalue of \(G-X\). Here \(G-X\) is the subgraph of \(G\) induced by \(V(G)\setminus X\), and it is called the star complement for \(\mu\). The main result of this paper is that a graph is exceptional if and only if it has an exceptional star complement for \(-2\). This result is then used to show that it is possible to find exceptional graphs using star complements for \(-2\), without any recourse to root systems. The authors also show that certain graphs with least eigenvalue \(-2\) can be characterized by star complements for \(-2\).

Recommendations

Cites work

Cited in

(26)

This page was built for publication: Graphs with least eigenvalue \(-2\): The star complement technique

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5949011)