Spectra of Graphs | springerprofessional.de

Springer Professional

nach oben

2012 | Buch

Kapitel lesen Erstes Kapitel lesen

Spectra of Graphs

verfasst von: Andries E. Brouwer, Willem H. Haemers

Verlag: Springer New York

Buchreihe : Universitext

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book gives an elementary treatment of the basic material about graph spectra, both for ordinary, and Laplace and Seidel spectra. The text progresses systematically, by covering standard topics before presenting some new material on trees, strongly regular graphs, two-graphs, association schemes, p-ranks of configurations and similar topics. Exercises at the end of each chapter provide practice and vary from easy yet interesting applications of the treated theory, to little excursions into related topics. Tables, references at the end of the book, an author and subject index enrich the text.

Spectra of Graphs is written for researchers, teachers and graduate students interested in graph spectra. The reader is assumed to be familiar with basic linear algebra and eigenvalues, although some more advanced topics in linear algebra, like the Perron-Frobenius theorem and eigenvalue interlacing are included.

Anzeige

Inhaltsverzeichnis

Frontmatter

Chapter 1. Graph Spectrum

Abstract

This chapter presents some simple results on graph spectra.We assume the reader is familiar with elementary linear algebra and graph theory. Throughout, J will denote the all-1 matrix, and 1 is the all-1 vector.

Andries E. Brouwer, Willem H. Haemers

Chapter 2. Linear Algebra

Abstract

In this chapter we present some less elementary but relevant results from linear algebra.

Andries E. Brouwer, Willem H. Haemers

Chapter 3. Eigenvalues and Eigenvectors of Graphs

Abstract

In this chapter, we apply the linear algebra from the previous chapter to graph spectra.

Andries E. Brouwer, Willem H. Haemers

Chapter 4. The Second-Largest Eigenvalue

Abstract

There is a tremendous amount of literature about the second-largest eigenvalue of a regular graph. If the gap between the largest and second-largest eigenvalues is large, then the graph has good connectivity, expansion and randomness properties. (About connectivity, see also §1.7.)

Andries E. Brouwer, Willem H. Haemers

Chapter 5. Trees

Abstract

Trees have a simpler structure than general graphs, and we can prove stronger results. For example, interlacing tells us that the multiplicity of an eigenvalue decreases by at most one when a vertex is removed. For trees Godsil’s lemma gives the same conclusion also when a path is removed.

Andries E. Brouwer, Willem H. Haemers

Chapter 6. Groups and Graphs

Abstract

Let G be a finite group, H a subgroup, and S a subset of G. We can define a graph Г (G,H,S) by taking as vertices the cosets gH (g ∈ G) and calling g1H and g2H adjacent when \(Hg_2^{-1} g1H \subseteq HSH\). The group G acts as a group of automorphisms on Г(G,H,S) via left multiplication, and this action is transitive. The stabilizer of the vertex H is the subgroup H. A graph Γ (G,H,S) with H = 1 is called a Cayley graph.

Andries E. Brouwer, Willem H. Haemers

Chapter 7. Topology

Abstract

In our discussion of the Shannon capacity (§3.7), we encountered the Haemers invariant, the minimum possible rank for certain matrices that fit a given graph. By far the most famous such invariant is the Colin de Verdière invariant of a graph, an algebraic invariant that turns out to have a topological meaning.

Andries E. Brouwer, Willem H. Haemers

Chapter 8. Euclidean Representations

Abstract

The main goal of this chapter is the famous result of CAMERON, GOETHALS, SEIDEL & SHULT [84] characterizing graphs with smallest eigenvalue not less than -2.

Andries E. Brouwer, Willem H. Haemers

Chapter 9. Strongly Regular Graphs

Abstract

A graph (simple, undirected, and loopless) of order v is called strongly regular with parameters v, k,λ,μ whenever it is not complete or edgeless.

Andries E. Brouwer, Willem H. Haemers

Chapter 10. Regular Two-graphs

Abstract

Let us call a graph (possibly improper) strongly regular when it is strongly regular or complete or edgeless.

Andries E. Brouwer, Willem H. Haemers

Chapter 11. Association Schemes

Abstract

An association scheme with d classes is a finite set X together with d +1 relations Ri on X such that

Andries E. Brouwer, Willem H. Haemers

Chapter 12. Distance-Regular Graphs

Abstract

Consider a connected simple graph with vertex set X of diameter d. Define Ri X2 by (x, y) Ri whenever x and y have graph distance

Andries E. Brouwer, Willem H. Haemers

Chapter 13. p-ranks

Abstract

Designs or graphs with the same parameters can sometimes be distinguished by considering the p-rank of associated matrices. For example, there are three nonisomorpic 2-(16,6,2) designs, with point-block incidence matrices of 2-rank 6, 7 and 8, respectively.

Andries E. Brouwer, Willem H. Haemers

Chapter 14. Spectral Characterizations

Abstract

In this chapter, we consider the question to what extent graphs are determined by their spectrum. First we give several constructions of families of cospectral graphs and then give cases in which it has been shown that the graph is determined by its spectrum.

Andries E. Brouwer, Willem H. Haemers

Chapter 15. Graphs with Few Eigenvalues

Abstract

Graphs with few distinct eigenvalues tend to have some kind of regularity. A graph with only one eigenvalue (for A, L, or Q) is edgeless, and a connected graph with two distinct adjacency eigenvalues (for A, L, or Q) is complete.

Andries E. Brouwer, Willem H. Haemers

Backmatter

Titel: Spectra of Graphs
verfasst von: Andries E. Brouwer
Willem H. Haemers
Copyright-Jahr: 2012
Verlag: Springer New York
Electronic ISBN: 978-1-4614-1939-6
Print ISBN: 978-1-4614-1938-9
DOI: https://doi.org/10.1007/978-1-4614-1939-6

Weitere Formate
Fachgebiete
Bücher
Zeitschriften
Themenseiten
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024