A brief introduction to spectral graph theory (Q1643530): Difference between revisions

This book provides a concise introduction to spectral graph theory and its applications. It is essentially divided into two halves: the first half of the book sets the scene with background on graph theory and related fields to which spectral graph theory can be applied. The second half treats the theory of graph spectra and various applications of spectral graph theory. In the first chapter, the reader is familiarised with basic notions of graph theory, and a few examples of special graphs are presented. The second chapter discusses graph invariants that can be studied using techniques of spectral graph theory: chromatic number, independence number, diameter and girth, and the isoperimetic number. The third chapter covers regular graphs, with a special focus on Cayley graphs. Thereafter, the book briefly leaves the realm of pure graph theory and covers finite fields, in particular squares in finite fields, and characters of finite abelian groups with an emphasis on characters of finite fields. Starting with Chapter 7, the reader learns about spectral graph theory and its applications. First, eigenvalues of the adjacency matrix and Laplacian matrix are introduced, and a few basic properties and examples are presented. Next, the author discusses methods to compute eigenvalues of special classes of regular graphs, such as Cayley graphs and strongly regular graphs. Chapter 9 treats the largest eigenvalues of the adjacency matrix and the Laplacian matrix, in particular various bounds and extremal results involving these eigenvalues. In Chapter 10, the study is extended to all eigenvalues of a graph, again providing various bounds. Chapter 11 exhibits spectral methods to study some of the purely graph-theoretical concepts that were covered in the early chapters. Specifically, one learns about spectral bounds for the chromatic number, the independence number, the isoperimetric constant and certain edge counts. The closing chapter covers further selected topics of spectral graph theory: the largest eigenvalue of \(C_4\)-free graphs, and eigenvalues of Erdős-Rényi graphs. This book can be recommended as a textbook for a first course on spectral graph theory, suitable for advanced undergraduate students. Each chapter also contains a number of exercises whose solutions are given at the end of the book.