×

Graphs with least eigenvalue \(-2\): a new proof of the 31 forbidden subgraphs theorem. (English) Zbl 1063.05090

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 P. J. Cameron, J. M. Goethals, J. J. Seidel and 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 [D. Cvetković, M. Doob and S. Simić, J. Graph Theory 5, 385-399 (1981; Zbl 0475.05061)], and independently by 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.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[6] P. J. Cameron and J. H. van Lint, Designs, Graphs, Codes and their Links, Cambridge University Press (1991). · Zbl 0743.05004
[13] D. Cvetković, P. Rowlinson and S. Simić, Eigenspaces of Graph}, Cambridge University Press (1997).
[17] A. J. Hoffman, -1-, Combinatorial Structures and their Applications, R. Guy, H. Hanani, N. Sauer and J. Schönheim (eds). Proc. Calgary Internat. Conf. on Combinatorial Structures and their Applications, Univ. Calgary, June 1969, Gordon and Breach, New York (1970) pp. 173–176.
[19] S. B. Rao, N. M. Singhi and K. S. Vijayan, The minimal forbidden subgraphs for generalized line graphs, Combinatorics and Graph Theory, Proc. Second Symp., Indian Statistical Institute, Calcutta, 22–29 February (1980) Lecture Notes in Math., Vol.885, S.B. Rao (ed.), Springer-Verlag, Berlin (1981) pp. 459–472.
[20] S. Simić, Contributions to the investigations of graph operations (Serbian) Ph.D. Thesis, Univ. Belgrade (1979).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.