Spectral Generalizations of Line Graphs: On Graphs with Least Eigenvalue -2 (London Mathematical Society Lecture Note Series)

Line graphs have the property that their least eigenvalue is greater than or equal to –2, a property shared by generalized line graphs and a finite number of so-called exceptional graphs. This book deals with all these families of graphs in the context of their spectral properties. The authors discuss the three principal techniques that have been employed, namely 'forbidden subgraphs', 'root systems' and 'star complements'. They bring together the major results in the area, including the recent construction of all the maximal exceptional graphs. Technical descriptions of these graphs are included in the appendices, while the bibliography provides over 250 references. This will be an important resource for all researchers with an interest in algebraic graph theory. Contents......Page 8 Preface......Page 10 1.1 Basic notions and results......Page 14 1.2 Some general theorems from spectral graph theory......Page 23 1.3 Elementary spectral characterizations......Page 34 1.4 A history of research on graphs with least eigenvalue......Page 35 2.1 Line graphs......Page 38 2.2 The eigenspace of 2 for generalized line graphs......Page 41 2.3 Generalized line graphs......Page 44 2.4 Some other classes of graphs......Page 57 2.5 General characterizations......Page 64 2.6 Spectral characterizations of regular line graphs......Page 67 3.1 Gram matrices and systems of lines......Page 77 3.2 Some properties of......Page 82 3.3 Extensions of line systems......Page 85 3.4 Smith graphs and line systems......Page 90 3.5 An alternative approach......Page 94 3.6 General characterization theorems......Page 96 3.7 Comments on some results from Chapter 2......Page 99 4.1 Regular exceptional graphs......Page 101 4.2 Characterizing regular line graphs by their spectra......Page 104 4.3 Special characterization theorems......Page 109 4.4 Regular exceptional graphs: computer investigations......Page 113 5.1 Basic properties......Page 125 5.2 Graph foundations......Page 137 5.3 Exceptional graphs......Page 142 5.4 Characterizations......Page 144 5.5 Switching......Page 149 6.1 The computer search......Page 152 6.2 Representations in......Page 155 6.3 A versatile star complement......Page 159 6.4 Graphs with maximal degree less than 28......Page 162 6.5 The last subcase......Page 166 6.6 Concluding remarks......Page 174 7.1 Graphs with second largest eigenvalue not exceeding 1......Page 177 7.2 Graphs sharing properties with their complements......Page 183 7.3 Spectrally bounded graphs......Page 189 7.4 Embedding a graph in a regular graph......Page 191 7.5 Reconstructing the characteristic polynomial......Page 193 7.6 Integral graphs......Page 196 7.7 Graph equations......Page 201 7.8 Other topics......Page 203 Appendix......Page 206 Bibliography......Page 294 Index......Page 308 Line graphs have the property that their least eigenvalue is greater than, or equal to, -2, a property shared by generalized line graphs and a finite number of so-called exceptional graphs. This book deals with all these families of graphs in the context of their spectral properties. Technical descriptions of these graphs are included in the appendices, while the bibliography provides over 250 references. It will be an important resource for all researchers with an interest in algebraic graph theory. This work discusses the three major techniques for the study of line graphs and generalized line graphs, namely 'forbidden subgraphs', 'root systems' and 'star complements', and it aims to bring together all the principal results of this area. An important resource for all researchers with an interest in algebraic graph theory. In Section 1.1 we introduce notation and terminology which will be used throughout the book.