Spectra of Graphs. Theory and Applications

Cover
Title page
Preface
0. Introduction
0.1. What the spectrum of a graph is and how it is presented in this book
0.2. Some more graph theoretic notions and conventions
0.3. Some theorems from matrix theory and their application to the spectrum of a graph
1. Basic Properties of the Spectrum of a Graph
1.1. The adjacency matrix and the (ordinary) spectrum of a graph
1.2. A general method for defining different kinds of graph spectra
1.3. Some remarks concerning current spectra
1.4. The coefficients of P_G(λ)
1.5. The coefficients of C_G(λ)
1.6. The coefficients of Q_G(λ)
1.7. A formula connecting the cyclic structure and the tree structure of a regular or semiregular muItigraph
1.8. On the number of walks
1.9. Miscellaneous results and problems
2. Operations on Graphs and the Resulting Spectra
2.1. The polynomial of a graph
2.2. The spectrum of the complement, direct sum, and complete product of graphs
2.3. Reduction procedures for calculating the characteristic polynomial
2.4. Line graphs and total graphs
2.5. NEPS and Boolean functions
2.6. The determination of characteristic polynomials and spectra of graphs of some particular types
2.7. Miscellaneous results and problems
3. Relations Between Spectral and Structural Properties of Graphs
3.1. Digraphs
3.2. Graphs
3.3. Regular graphs
3.4. Some remarks on strongly regular graphs
3.5. Eigenvectors
3.6. Miscellaneous results and problems
4. The Divisor of a Graph
4.1. The divisor concept
4.2. Divisor and cover
4.3. A generalization of the divisor concept
4.4. Symmetry properties and divisors of graphs
4.5. The fundamentallemma connecting the divisor and the spectrum
4.6. The divisor - an effective tool for factoring the characteristic polynomial
4.7. The divisor - a mediator between structure and spectrum
4.8. Miscellaneous results and problems
5. The Spectrum and the Group of Automorphisms
5.1. Symmetry and simple eigenvalues
5.2. The spectrum and representations of the automorphism group
5.3. The front divisor induced by a subgroup of the automorphism group
5.4. Cospectral graphs with prescribed (distinct) automorphism groups
5.5. Miscellaneous results and problems
6. Characterization of Graphs by Means of Spectra
6.1. Some familles of non-isomorphic cospectral graphs
6.2. The characterization of a graph by its spectrum
6.3. The characterization and other spectral properties of line graphs
6.4. Metrically regular graphs
6.5. The (-l, l, 0 )-adjacency matrix and Seidel switching
6.6. Miscellaneous results and problems
7. Spectral Techniques in Graph Theory and Combinatorics
7.1. The existence and the non-existence of certain combinatorial objects
7.2. Strongly regular graphs and distance-transitive graphs
7.3. Equiangular lin es and two-graphs
7.4. Connectedness and bipartiteness of certain graph products
7.5. Determination of the number of walks
7.6. Determiantion of the number of spanning trees
7.7. External problems
7.8. Miscellaneous results and problems
8. Applications in Chemistry and Physics
8.1. Hückel's theory
8.2. Graphs related to benzenoid hydrocarbons
8.3. The dimer problem
8.4. Vibration of a membrane
8.5. Miscellaneous results and problems
9. Some Additional Results
9.1. Eigenvalues and imbeddings
9.2. The distance polynomial
9.3. The algebraic connectivity of a graph
9.4. Integral graphs
9.5. Some problems
Appendix. Tables of Graph Spectra
Bibliography
Index of Symbols
Index of Names
Subject Index
Appendix A. Comments on the First Two Editions of the Book
Appendix B. Recent Developments in the Theory of Graph Spectra
B.1 A survey of relevant books
B.2 Expository papers
B.3 Graphs with least eigenvalue -2
B.4 Largest eigenvalue
B.5 Second largest eigenvalue
B.6 Distance-regular graphs
B.6.1 Strongly regular graphs
B.6.2 Other distance-regular graphs
B.7 Graph angles and star partitions
B.7.1 Examples and introducing comments
B.7.2 Some properties of graph angles
B.7.3 Main angles
B.7.4 EA-reconstruction of trees
B.7.5 Ulam's reconstruction conjecture for graphs
B.7.6 Star partitions and canonical star bases
B.8 Graph Laplacians
B.9 Tables of graph spectra
B.10 The expert system GRAPH and the computer program GRAFFITI
B.10.1 System GRAPH
B.10.2 Program GRAFFITI
B.11 Graph spectra and combinatorial optimization
B.12 Miscellaneous results
Additional Bibliography