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.
Author(s): Cvetkovic D., Rowlinson P., Simic S.
Series: London Mathematical Society Lecture Note Series
Publisher: CUP
Year: 2004
Language: English
Pages: 311
Tags: Математика;Дискретная математика;Теория графов;
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
