Star complements and exceptional graphs

DOI10.1016/J.LAA.2007.01.008MaRDI QIDQ876316zbMATH OpenOpenAlexFDO

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

Publication date 18 April 2007

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.laa.2007.01.008

zbMATH Keywords

eigenvalue graph star complement

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Review text

Let \(G\) be a finite graph of order \(n\) with an eigenvalue \(\mu\) of multiplicity \(k\). (Thus the \(\mu\)-eigenspace of a \((0,1)\)-adjacency matrix of \(G\) has dimension \(k\).) A star complement for \(\mu\) in \(G\) is an induced subgraph \(G-X\) of \(G\) such that \(| X| =k\) and \(G-X\) does not have \(\mu\) as an eigenvalue. An exceptional graph is a connected graph, other than a generalized line graph, whose eigenvalues lie in \([-2,\infty)\). The authors investigate properties of star sets and star complements related to graphs with least eigenvalue \(-2\), and explain some phenomena observed from earlier computer results. Explicitly, they give a simple computer-free proof that each exceptional graph with least eigenvalue greater than \(-2\) is an induced subgraph of an exceptional graph with least eigenvalue equal to \(-2\). They also show how extendability graphs can be used to investigate the regular exceptional graphs. Finally, they establish a property of eigenvectors of exceptional graphs with \(-2\) as a simple eigenvalue.

Recommendations

Cites work

Cited in

(21)

This page was built for publication: Star complements and exceptional graphs

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