Coverart for item
The Resource Spectra of graphs, by Andries E. Brouwer, Willem H. Haemers

Spectra of graphs, by Andries E. Brouwer, Willem H. Haemers

Label
Spectra of graphs
Title
Spectra of graphs
Statement of responsibility
by Andries E. Brouwer, Willem H. Haemers
Creator
Contributor
Subject
Language
eng
http://library.link/vocab/creatorName
Brouwer, A. E.
Illustrations
illustrations
Index
no index present
Literary form
non fiction
http://library.link/vocab/relatedWorkOrContributorName
Haemers, W. H
Series statement
Universitext
http://library.link/vocab/subjectName
  • Graph theory
  • Spectral theory (Mathematics)
Label
Spectra of graphs, by Andries E. Brouwer, Willem H. Haemers
Instantiates
Publication
Contents
1.1. Matrices associated to a graph -- 1.2. The spectrum of a graph -- 1.2.1. Characteristic polynomial -- 1.3. The spectrum of an undirected graph -- 1.3.1. Regular graphs -- 1.3.2. Complements -- 1.3.3. Walks -- 1.3.4. Diameter -- 1.3.5. Spanning trees -- 1.3.6. Bipartite graphs -- 1.3.7. Connectedness -- 1.4. Spectrum of some graphs -- 1.4.1. The complete graph -- 1.4.2. The complete bipartite graph -- 1.4.3. The cycle -- 1.4.4. The path -- 1.4.5. Line graphs -- 1.4.6. Cartesian products -- 1.4.7. Kronecker products and bipartite double -- 1.4.8. Strong products -- 1.4.9. Cayley graphs -- 1.5. Decompositions -- 1.5.1. Decomposing K10 into Petersen graphs -- 1.5.2. Decomposing Kn into complete bipartite graphs -- 1.6. Automorphisms -- 1.7. Algebraic connectivity -- 1.8. Cospectral graphs -- 1.8.1. The 4-cube -- 1.8.2. Seidel switching -- 1.8.3. Godsil-McKay switching -- 1.8.4. Reconstruction -- 1.9. Very small graphs -- 1.10. Exercises -- 2.1. Simultaneous diagonalization -- 2.2. Perron-Frobenius theory -- 2.3. Equitable partitions -- 2.3.1. Equitable and almost equitable partitions of graphs -- 2.4. The Rayleigh quotient -- 2.5. Interlacing -- 2.6. Schur's inequality -- 2.7. Schur complements -- 2.8. The Courant-Weyl inequalities -- 2.9. Gram matrices -- 2.10. Diagonally dominant matrices -- 2.10.1. Ger[š]gorin circles -- 2.11. Projections -- 2.12. Exercises -- 3.1. The largest eigenvalue -- 3.1.1. Graphs with largest eigenvalue at most 2 -- 3.1.2. Subdividing an edge -- 3.1.3. The Kelmans operation -- 3.2. Interlacing -- 3.3. Regular graphs -- 3.4. Bipartite graphs -- 3.5. Cliques and cocliques -- 3.5.1. Using weighted adjacency matrices -- 3.6. Chromatic number -- 3.6.1. Using weighted adjacency matrices -- 3.6.2. Rank and chromatic number -- 3.7. Shannon capacity -- 3.7.1. Lovász's v-function -- 3.7.2. The Haemers bound on the Shannon capacity -- 3.8. Classification of integral cubic graphs -- 3.8.1. A quotient of the hexagonal grid -- 3.8.2. Cubic graphs with loops -- 3.8.3. The classification -- 3.9. The largest Laplace eigenvalue -- 3.10. Laplace eigenvalues and degrees -- 3.11. The Grone-Merris conjecture -- 3.11.1. Threshold graphs -- 3.11.2. Proof of the Grone-Merris conjecture -- 3.12. The Laplacian for hypergraphs -- 3.12.1. Dominance order -- 3.13. Applications of eigenvectors -- 3.13.1. Ranking -- 3.13.2. Google PageRank -- 3.13.3. Cutting -- 3.13.4. Graph drawing -- 3.13.5. Clustering -- 3.13.6. Graph isomorphism -- 3.13.7. Searching an eigenspace -- 3.14. Stars and star complements -- 3.15. Exercises -- 4.1. Bounds for the second-largest eigenvalue -- 4.2. Large regular subgraphs are connected -- 4.3. Randomness -- 4.4. Random walks -- 4.5. Expansion -- 4.6. Toughness and Hamiltonicity -- 4.6.1. The Petersen graph is not Hamiltonian -- 4.7. Diameter bound -- 4.8. Separation -- 4.8.1. Bandwidth -- 4.8.2. Perfect matchings -- 4.9. Block designs -- 4.10. Polarities -- 4.11. Exercises -- 5.1. Characteristic polynomials of trees -- 5.2. Eigenvectors and multiplicities -- 5.3. Sign patterns of eigenvectors of graphs -- 5.4. Sign patterns of eigenvectors of trees -- 5.5. The spectral center of a tree -- 5.6. Integral trees -- 5.7. Exercises -- 6.1. γ(G,H,S) -- 6.2. Spectrum -- 6.3. Non-Abelian Cayley graphs -- 6.4. Covers -- 6.5. Cayley sum graphs -- 6.5.1. (3,6)-fullerenes -- 6.6. Exercises -- 7.1. Embeddings -- 7.2. Minors -- 7.3. The Colin de Verdière invariant -- 7.4. The Van der Holst-Laurent-Schrijver invariant -- 8.1. Examples -- 8.2. Euclidean representation -- 8.3. Root lattices -- 8.3.1. Examples -- 8.3.2. Root lattices -- 8.3.3. Classification -- 8.4. The Cameron-Goethals-Seidel-Shull theorem -- 8.5. Further applications -- 8.6. Exercises -- 9.1. Strongly regular graphs -- 9.1.1. Simple examples -- 9.1.2. The Paley graphs -- 9.1.3. Adjacency matrix -- 9.1.4. Imprimitive graphs -- 9.1.5. Parameters -- 9.1.6. The half case and cyclic strongly regular graphs -- 9.1.7. Strongly regular graphs without triangles. -- 9.1.8. Further parameter restrictions -- 9.1.9. Strongly regular graphs from permutation groups -- 9.1.10. Strongly regular graphs from quasisymmetric designs -- 9.1.11. Symmetric 2-designs from strongly regular graphs -- 9.1.12. Latin square graphs -- 9.1.13. Partial geometries -- 9.2. Strongly regular graphs with eigenvalue-2 -- 9.3. Connectivity -- 9.4. Cocliques and colorings -- 9.5. Automorphisms -- 9.6. Generalized quadrangles -- 9.6.1. Parameters -- 9.6.2. Constructions of generalized quadrangles -- 9.6.3. Strongly regular graphs from generalized quadrangles -- 9.6.4. Generalized quadrangles with lines of size 3 -- 9.7. The (81, 20, 1, 6) strongly regular graph -- 9.7.1. Descriptions -- 9.7.2. Uniqueness -- 9.7.3. Independence and chromatic numbers -- 9.7.4. Second subconstituent -- 9.8. Strongly regular graphs and two-weight codes -- 9.8.1. Codes, graphs, and projective sets -- 9.8.2. The correspondence between linear codes and subsets of a projective space -- 9.8.3. The correspondence between projective two-weight codes, subsets of a projective space with two intersection numbers, and affine strongly regular graphs -- 9.8.4. Duality for affine strongly regular graphs -- 9.8.5. Cyclotomy -- 9.9. Table of parameters for strongly regular graphs -- 9.9.1. Comments -- 9.10. Exercises -- 10.1. Strong graphs -- 10.2. Two-graphs -- 10.3. Regular two-graphs -- 10.3.1. Related strongly regular graphs -- 10.3.2. The regular two-graph on 276 points -- 10.3.3. Coherent subsets -- 10.3.4. Completely regular two-graphs -- 10.4. Conference matrices -- 10.5. Hadamard matrices -- 10.5.1. Constructions -- 10.6. Equiangular lines -- 10.6.1. Equiangular lines in Rd and two-graphs -- 10.6.2. Bounds on equiangular sets of lines in Rd or Cd -- 10.6.3. Bounds on sets of lines with few angles and sets of vectors with few distances -- 11.1. Definition -- 11.2. The Bose-Mesner algebra -- 11.3. The linear programming bound -- 11.3.1. Equality -- 11.3.2. The code-clique theorem -- 11.3.3. Strengthened LP bounds -- 11.4. The Krein parameters -- 11.5. Automorphisms -- 11.5.1. The Moore graph on 3250 vertices -- 11.6. P- and Q-polynomial association schemes -- 11.7. Exercises -- 12.1. Parameters -- 12.2. Spectrum -- 12.3. Primitivity -- 12.4. Examples -- 12.4.1. Hamming graphs -- 12.4.2. Johnson graphs -- 12.4.3. Grassmann graphs -- 12.4.4. Van Dam-Koolen graphs -- 12.5. Bannai-Ito conjecture -- 12.6. Connectedness -- 12.7. Growth -- 12.8. Degree of eigenvalues -- 12.9. Moore graphs and generalized polygons -- 12.10. Euclidean representations -- 12.11. Extremality -- 12.12. Exercises -- 13.1. Reduction mod p -- 13.2. The minimal polynomial -- 13.3. Bounds for the p-rank -- 13.4. Interesting primes p -- 13.5. Adding a multiple of J -- 13.6. Paley graphs -- 13.7. Strongly regular graphs -- 13.8. Smith normal form -- 13.8.1. Smith normal form and spectrum -- 13.9. Exercises -- 14.1. Generalized adjacency matrices -- 14.2. Constructing cospectral graphs -- 14.2.1. Trees -- 14.2.2. Partial linear spaces -- 14.2.3. GM switching -- 14.2.4. Sunada's method -- 14.3. Enumeration -- 14.3.1. Lower bounds -- 14.3.2. Computer results -- 14.4. DS graphs -- 14.4.1. Spectrum and structure -- 14.4.2. Some DS graphs -- 14.4.3. Line graphs -- 14.5. Distance-regular graphs -- 14.5.1. Strongly regular DS graphs -- 14.5.2. Distance-regularity from the spectrum -- 14.5.3. Distance-regular DS graphs -- 14.6. The method of Wang and Xu -- 14.7. Exercises -- 15.1. Regular graphs with four eigenvalues -- 15.2. Three Laplace eigenvalues -- 15.3. Other matrices with at most three eigenvalues -- 15.3.1. Few Seidel eigenvalues -- 15.3.2. Three adjacency eigenvalues -- 15.3.3. Three signless Laplace eigenvalues -- 15.4. Exercises
Control code
ocn761381086
Dimensions
25 cm
Extent
xiii, 250p.
Isbn
9781461419389
Isbn Type
(hbk.)
Other physical details
ill.
System control number
(OCoLC)761381086
Label
Spectra of graphs, by Andries E. Brouwer, Willem H. Haemers
Publication
Contents
1.1. Matrices associated to a graph -- 1.2. The spectrum of a graph -- 1.2.1. Characteristic polynomial -- 1.3. The spectrum of an undirected graph -- 1.3.1. Regular graphs -- 1.3.2. Complements -- 1.3.3. Walks -- 1.3.4. Diameter -- 1.3.5. Spanning trees -- 1.3.6. Bipartite graphs -- 1.3.7. Connectedness -- 1.4. Spectrum of some graphs -- 1.4.1. The complete graph -- 1.4.2. The complete bipartite graph -- 1.4.3. The cycle -- 1.4.4. The path -- 1.4.5. Line graphs -- 1.4.6. Cartesian products -- 1.4.7. Kronecker products and bipartite double -- 1.4.8. Strong products -- 1.4.9. Cayley graphs -- 1.5. Decompositions -- 1.5.1. Decomposing K10 into Petersen graphs -- 1.5.2. Decomposing Kn into complete bipartite graphs -- 1.6. Automorphisms -- 1.7. Algebraic connectivity -- 1.8. Cospectral graphs -- 1.8.1. The 4-cube -- 1.8.2. Seidel switching -- 1.8.3. Godsil-McKay switching -- 1.8.4. Reconstruction -- 1.9. Very small graphs -- 1.10. Exercises -- 2.1. Simultaneous diagonalization -- 2.2. Perron-Frobenius theory -- 2.3. Equitable partitions -- 2.3.1. Equitable and almost equitable partitions of graphs -- 2.4. The Rayleigh quotient -- 2.5. Interlacing -- 2.6. Schur's inequality -- 2.7. Schur complements -- 2.8. The Courant-Weyl inequalities -- 2.9. Gram matrices -- 2.10. Diagonally dominant matrices -- 2.10.1. Ger[š]gorin circles -- 2.11. Projections -- 2.12. Exercises -- 3.1. The largest eigenvalue -- 3.1.1. Graphs with largest eigenvalue at most 2 -- 3.1.2. Subdividing an edge -- 3.1.3. The Kelmans operation -- 3.2. Interlacing -- 3.3. Regular graphs -- 3.4. Bipartite graphs -- 3.5. Cliques and cocliques -- 3.5.1. Using weighted adjacency matrices -- 3.6. Chromatic number -- 3.6.1. Using weighted adjacency matrices -- 3.6.2. Rank and chromatic number -- 3.7. Shannon capacity -- 3.7.1. Lovász's v-function -- 3.7.2. The Haemers bound on the Shannon capacity -- 3.8. Classification of integral cubic graphs -- 3.8.1. A quotient of the hexagonal grid -- 3.8.2. Cubic graphs with loops -- 3.8.3. The classification -- 3.9. The largest Laplace eigenvalue -- 3.10. Laplace eigenvalues and degrees -- 3.11. The Grone-Merris conjecture -- 3.11.1. Threshold graphs -- 3.11.2. Proof of the Grone-Merris conjecture -- 3.12. The Laplacian for hypergraphs -- 3.12.1. Dominance order -- 3.13. Applications of eigenvectors -- 3.13.1. Ranking -- 3.13.2. Google PageRank -- 3.13.3. Cutting -- 3.13.4. Graph drawing -- 3.13.5. Clustering -- 3.13.6. Graph isomorphism -- 3.13.7. Searching an eigenspace -- 3.14. Stars and star complements -- 3.15. Exercises -- 4.1. Bounds for the second-largest eigenvalue -- 4.2. Large regular subgraphs are connected -- 4.3. Randomness -- 4.4. Random walks -- 4.5. Expansion -- 4.6. Toughness and Hamiltonicity -- 4.6.1. The Petersen graph is not Hamiltonian -- 4.7. Diameter bound -- 4.8. Separation -- 4.8.1. Bandwidth -- 4.8.2. Perfect matchings -- 4.9. Block designs -- 4.10. Polarities -- 4.11. Exercises -- 5.1. Characteristic polynomials of trees -- 5.2. Eigenvectors and multiplicities -- 5.3. Sign patterns of eigenvectors of graphs -- 5.4. Sign patterns of eigenvectors of trees -- 5.5. The spectral center of a tree -- 5.6. Integral trees -- 5.7. Exercises -- 6.1. γ(G,H,S) -- 6.2. Spectrum -- 6.3. Non-Abelian Cayley graphs -- 6.4. Covers -- 6.5. Cayley sum graphs -- 6.5.1. (3,6)-fullerenes -- 6.6. Exercises -- 7.1. Embeddings -- 7.2. Minors -- 7.3. The Colin de Verdière invariant -- 7.4. The Van der Holst-Laurent-Schrijver invariant -- 8.1. Examples -- 8.2. Euclidean representation -- 8.3. Root lattices -- 8.3.1. Examples -- 8.3.2. Root lattices -- 8.3.3. Classification -- 8.4. The Cameron-Goethals-Seidel-Shull theorem -- 8.5. Further applications -- 8.6. Exercises -- 9.1. Strongly regular graphs -- 9.1.1. Simple examples -- 9.1.2. The Paley graphs -- 9.1.3. Adjacency matrix -- 9.1.4. Imprimitive graphs -- 9.1.5. Parameters -- 9.1.6. The half case and cyclic strongly regular graphs -- 9.1.7. Strongly regular graphs without triangles. -- 9.1.8. Further parameter restrictions -- 9.1.9. Strongly regular graphs from permutation groups -- 9.1.10. Strongly regular graphs from quasisymmetric designs -- 9.1.11. Symmetric 2-designs from strongly regular graphs -- 9.1.12. Latin square graphs -- 9.1.13. Partial geometries -- 9.2. Strongly regular graphs with eigenvalue-2 -- 9.3. Connectivity -- 9.4. Cocliques and colorings -- 9.5. Automorphisms -- 9.6. Generalized quadrangles -- 9.6.1. Parameters -- 9.6.2. Constructions of generalized quadrangles -- 9.6.3. Strongly regular graphs from generalized quadrangles -- 9.6.4. Generalized quadrangles with lines of size 3 -- 9.7. The (81, 20, 1, 6) strongly regular graph -- 9.7.1. Descriptions -- 9.7.2. Uniqueness -- 9.7.3. Independence and chromatic numbers -- 9.7.4. Second subconstituent -- 9.8. Strongly regular graphs and two-weight codes -- 9.8.1. Codes, graphs, and projective sets -- 9.8.2. The correspondence between linear codes and subsets of a projective space -- 9.8.3. The correspondence between projective two-weight codes, subsets of a projective space with two intersection numbers, and affine strongly regular graphs -- 9.8.4. Duality for affine strongly regular graphs -- 9.8.5. Cyclotomy -- 9.9. Table of parameters for strongly regular graphs -- 9.9.1. Comments -- 9.10. Exercises -- 10.1. Strong graphs -- 10.2. Two-graphs -- 10.3. Regular two-graphs -- 10.3.1. Related strongly regular graphs -- 10.3.2. The regular two-graph on 276 points -- 10.3.3. Coherent subsets -- 10.3.4. Completely regular two-graphs -- 10.4. Conference matrices -- 10.5. Hadamard matrices -- 10.5.1. Constructions -- 10.6. Equiangular lines -- 10.6.1. Equiangular lines in Rd and two-graphs -- 10.6.2. Bounds on equiangular sets of lines in Rd or Cd -- 10.6.3. Bounds on sets of lines with few angles and sets of vectors with few distances -- 11.1. Definition -- 11.2. The Bose-Mesner algebra -- 11.3. The linear programming bound -- 11.3.1. Equality -- 11.3.2. The code-clique theorem -- 11.3.3. Strengthened LP bounds -- 11.4. The Krein parameters -- 11.5. Automorphisms -- 11.5.1. The Moore graph on 3250 vertices -- 11.6. P- and Q-polynomial association schemes -- 11.7. Exercises -- 12.1. Parameters -- 12.2. Spectrum -- 12.3. Primitivity -- 12.4. Examples -- 12.4.1. Hamming graphs -- 12.4.2. Johnson graphs -- 12.4.3. Grassmann graphs -- 12.4.4. Van Dam-Koolen graphs -- 12.5. Bannai-Ito conjecture -- 12.6. Connectedness -- 12.7. Growth -- 12.8. Degree of eigenvalues -- 12.9. Moore graphs and generalized polygons -- 12.10. Euclidean representations -- 12.11. Extremality -- 12.12. Exercises -- 13.1. Reduction mod p -- 13.2. The minimal polynomial -- 13.3. Bounds for the p-rank -- 13.4. Interesting primes p -- 13.5. Adding a multiple of J -- 13.6. Paley graphs -- 13.7. Strongly regular graphs -- 13.8. Smith normal form -- 13.8.1. Smith normal form and spectrum -- 13.9. Exercises -- 14.1. Generalized adjacency matrices -- 14.2. Constructing cospectral graphs -- 14.2.1. Trees -- 14.2.2. Partial linear spaces -- 14.2.3. GM switching -- 14.2.4. Sunada's method -- 14.3. Enumeration -- 14.3.1. Lower bounds -- 14.3.2. Computer results -- 14.4. DS graphs -- 14.4.1. Spectrum and structure -- 14.4.2. Some DS graphs -- 14.4.3. Line graphs -- 14.5. Distance-regular graphs -- 14.5.1. Strongly regular DS graphs -- 14.5.2. Distance-regularity from the spectrum -- 14.5.3. Distance-regular DS graphs -- 14.6. The method of Wang and Xu -- 14.7. Exercises -- 15.1. Regular graphs with four eigenvalues -- 15.2. Three Laplace eigenvalues -- 15.3. Other matrices with at most three eigenvalues -- 15.3.1. Few Seidel eigenvalues -- 15.3.2. Three adjacency eigenvalues -- 15.3.3. Three signless Laplace eigenvalues -- 15.4. Exercises
Control code
ocn761381086
Dimensions
25 cm
Extent
xiii, 250p.
Isbn
9781461419389
Isbn Type
(hbk.)
Other physical details
ill.
System control number
(OCoLC)761381086

Library Locations

    • Manawatū LibraryBorrow it
      Tennent Drive, Palmerston North, Palmerston North, 4472, NZ
      -40.385340 175.617349
Processing Feedback ...