Graphs with least eigenvalue \(-2\): a new proof of the 31 forbidden subgraphs theorem
type: Item
instance of: scholarly article
title: Graphs with least eigenvalue \(-2\): a new proof of the 31 forbidden subgraphs theorem
zbMATH Open document ID: 1063.05090
author: P. Rowlinson
author: Dragoš Cvetković
author: Slobodan K. Simić
published in: Designs, Codes and Cryptography
publication date: 2005-02-28T00:00:00Z
review text: An early observation that line graphs have least eigenvalue greater than or equal to \(-2\) led to the natural problem to characterize the graphs with this property. Such graphs turned out to be generalized line graphs and a few hundreds of exceptional graphs [see \textit{P. J. Cameron, J. M. Goethals, J. J. Seidel} and \textit{E. E. Shult}, J. Algebra 43, 305--327 (1976; Zbl 0337.05142)]. Generalized line graphs were later characterized by a collection of 31 forbidden induced subgraphs in [\textit{D. Cvetković, M. Doob} and \textit{S. Simić}, J. Graph Theory 5, 385-399 (1981; Zbl 0475.05061)], and independently by \textit{S. B. Rao} et al. [Proc. Symp., Calcutta 1980, Lect. Notes Math. 885, 459--472 (1981; Zbl 0494.05053)]. However, the existing proofs of this result are rather involved. The paper under review provides a new proof by introducing an edge-colouring technique for investigating minimal non-generalized line graphs. It is then shown that such a graph has at most 8 vertices.
reviewed by: Dragan Stevanović
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 2139255
zbMATH Keywords: graph spectrum
zbMATH Keywords: generalized line graphs
MaRDI profile type: Publication
full work available at URL: s10623-004-4856-5
OpenAlex ID: W1998386707
cites work: Characterizations of derived graphs
cites work: Line graphs, root systems, and elliptic geometry
cites work: Q4000288
cites work: Graphs with least eigenvalue \(-2\); a historical survey and recent developments in maximal exceptional graphs
cites work: Generalized line graphs
cites work: A table of connected graphs on six vertices
cites work: Graphs with least eigenvalue \(-2\): The star complement technique
cites work: On spectral characterization and embeddings of graphs
cites work: Graphs with eigenvalues at least - 2
DOI: 10.1007/S10623-004-4856-5
description: scientific article; zbMATH DE number 2139255