No label defined (Q4828550)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2117218
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 2117218 |
Statements
22 November 2004
0 references
adjacency matrix
0 references
spectrum
0 references
characteristic polynomial
0 references
generalized line graph
0 references
root system
0 references
star complement
0 references
0.9129083
0 references
0.9033226
0 references
0.8971643
0 references
0.8971318
0 references
0.8968464
0 references
0.89645445
0 references
0.8964197
0 references
0.89548814
0 references
The scope of this book is broader than its secondary title might suggest. Indeed, from the authors' preface: ``The eigenvalues discussed in this book are those of a \((0,1)\)-adjacency matrix of a finite undirected graph. Line graphs (\dots) have the property that their least eigenvalue is greater than or equal to \(-2\). This property is shared with generalized line graphs, which can be viewed as line graphs of certain multigraphs. Apart from these classes of examples there are only finitely many further connected graphs with spectrum in the interval \([-2,\infty)\), and these are called exceptional graphs \dots . Having worked in spectral graph theory for many years, the authors came to see the need for a single source of information on the principal results in this area.'' Chapter 1 contains a lengthy catalog of known results in spectral graph theory, stated with reference(s) but often without proof. Chapter 2 offers various characterizations of line graphs and generalized line graphs. Let \(H\) be a graph with \(VH=\{v_1,\dots,v_n\}\) and let \(a_1,\dots,a_n\in{N}\). The root multigraph \(\widehat{H}\) is obtained from \(H\) by adjoining \(a_i\) pendant 2-cycles to \(v_i\) \((i=1,\dots,n)\). The generalized line graph \(L(H;a_1,\dots,a_n)\) is the line graph \(L(\widehat{H})\). As the property for a graph to have least eigenvalue greater than or equal to \(-2\) is hereditary, the technique studied in this chapter is that of determining a finite collection of minimal forbidden subgraphs. Chapter 3 is based on the work of \textit{P. J. Cameron, J. M. Goethals, J. J. Seidel}, and \textit{E. E. Shult} [J. Algebra 43, 305--327 (1976; Zbl 0337.05142)] ``using systems of vectors which are called root systems in accordance with the theory of Lie algebras over \(C\).'' Here the exceptional graphs are characterized as non-generalized line graphs that are nonetheless representable in the root system \(E_8\) (8-dimensional Euclidean space). The techniques of this chapter are applied to regular graphs in Chapter 4. Chapter 5 presents star complements, the third and most recent of the three major techniques in this study of graphs with least eigenvalue \(-2\). This approach ``enables all of the maximal exceptional graphs to be constructed (Chapter 6).'' There are 473 of them, of which 187 are regular, and are described explicitly via seven tables and numerous figures in the 87-page appendix. The largest of these graphs has 36 vertices and maximum valence 28. Chapter 7 is a compendium of results that do not fit neatly into any of the above three approaches. Included are an extensive bibliography and a helpful index of symbols and terms. This is a deep and challenging piece of work. In addition to more than a basic acquaintance with graph theory, the reader requires as well a substantial background in linear algebra, geometry, and abstract algebra.
0 references