Authors: Cvetković, Dragoš
Rowlinson, Peter
Simić, Slobodan 
Title: Graphs with least eigenvalue -2: A new proof of the 31 forbidden subgraphs theorem
Journal: Designs, Codes, and Cryptography
Volume: 34
Issue: 2-3
First page: 229
Last page: 240
Issue Date: 1-Jan-2005
Rank: M22
ISSN: 0925-1022
DOI: 10.1007/s10623-004-4856-5
Generalized line graphs were introduced by Hoffman Proc. Calgary Internat. Conf. on Combinatorial Structures and their applications, Gordon and Breach, New York (1970); they were characterized in 1980 by a collection of 31 forbidden induced subgraphs, obtained independently by Cvetković et al., Comptes Rendus Math. Rep. Acad. Sci. Canada (1980) and S. B. Rao et al., Proc. Second Symp., Indian Statistical Institute, Calcutta, Lecture Notes in Math., (1981). Here a short new proof of this characterization theorem is given, based on an edge-colouring technique.
Keywords: Forbidden subgraphs | Generalized line graphs | Graph spectra | Least eigenvalue
Publisher: Springer Link

Show full item record


checked on Jun 24, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.