An introduction to the theory of graph spectra / Dragoš Cvetković, Peter Rowlinson, Slobodan Simić.

Format:

Book

Author/Creator:

Cvetković, Dragoš M.

Contributor:

Rowlinson, Peter.

Simić, S. (Slobodan)

London Mathematical Society.

Series:

London Mathematical Society student texts ; 74.

London Mathematical Society student texts ; 74

Language:

English

Subjects (All):

Graph theory.

Matrices.

Physical Description:

xi, 364 pages : illustrations ; 24 cm.

Place of Publication:

Cambridge : Cambridge University Press, 2010.

Summary:

This introductory text explores the theory of graph spectra: a topic with applications across a wide range of subjects, including computer science, quantum chemistry and electrical engineering. The spectra examined here are those of the adjacency matrix, the Seidel matrix, the Laplacian, the normalized Laplacian and the signless Laplacian of a finite simple graph. The underlying theme of the book is the relation between the eigenvalues and structure of a graph.

Designed as an introductory text for graduate students, or anyone using the theory of graph spectra, this self-contained, treatment assumes only a little knowledge of graph theory and linear algebra. The authors include many new developments in the field that arise as a result of rapidly expanding interest in the area. Exercises, spectral data and proofs of required results are also provided. The end-of-chapter notes serve as a practical guide to the extensive bibliography of over 500 items.

Contents:

1 Introduction 1

1.1 Graph spectra 1

1.2 Some more graph-theoretic notions 6

1.3 Some results from linear algebra 11

Exercises 21

Notes 23

2 Graph operations and modifications 24

2.1 Complement, union and join of graphs 24

2.2 Coalescence and related graph compositions 29

2.3 General reduction procedures 35

2.4 Line graphs and related operations 38

2.5 Cartesian type operations 43

2.6 Spectra of graphs of particular types 46

Exercises 49

Notes 51

3 Spectrum and structure 52

3.1 Counting certain subgraphs 52

3.2 Regularity and bipartiteness 55

3.3 Connectedness and metric invariants 58

3.4 Line graphs and related graphs 60

3.5 More on regular graphs 65

3.6 Strongly regular graphs 70

3.7 Distance-regular graphs 76

3.8 Automorphisms and eigenspaces 80

3.9 Equitable partitions, divisors and main eigenvalues 83

3.10 Spectral bounds for graph invariants 87

3.11 Constraints on individual eigenvalues 91

Exercises 100

Notes 102

4 Characterizations by spectra 104

4.1 Speclial characterizations of certain classes of graphs 104

4.2 Cospectral graphs and the graph isomorphism problem 118

4.3 Characterizations by eigenvalues and angles 126

Exercises 133

Notes 134

5 Structure and one eigenvalue 136

5.1 Star complements 136

5.2 Construction and characterization 141

5.3 Bounds on multiplicities 150

5.4 Graphs with least eigenvalue-2 154

5.5 Graph foundations 155

Exercises 160

Notes 161

6 Spectral techniques 162

6.1 Decompositions of complete graphs 162

6.2 Graph homomorphisms 165

6.3 The Friendship Theorem 167

6.4 Moore graphs 169

6.5 Generalized quadrangles 172

6.6 Equiangular lines 174

6.7 Counting walks 179

Exercises 182

Notes 183

7 Laplacians 184

7.1 The Laplacian spectrum 184

7.2 The Matrix-Tree Theorem 189

7.3 The largest eigenvalue 193

7.4 Algebraic connectivity 197

7.5 Laplacian eigenvalues and graph structure 199

7.6 Expansion 208

7.7 The normalized Laplacian matrix 212

7.8 The signless Laplacian 216

Exercises 225

Notes 226

8 Some additional results 228

8.1 More on graph eigenvalues 228

8.2 Eigenvectors and structure 243

8.3 Reconstructing the characteristic polynomial 250

8.4 Integral graphs 254

Exercises 257

Notes 258

9 Applications 259

9.1 Physics 259

9.2 Chemistry 266

9.3 Computer science 273

9.4 Mathematics 277

Notes 283.

Notes:

Includes bibliographical references and indexes.

ISBN:

9780521118392

0521118395

9780521134088

0521134080

OCLC:

463633465