A brief introduction to spectral graph theory
adjacency eigenvalues of graphsalgebraic graphs over finite fieldsCayley graphscharacter sumsLaplacian eigenvalues of graphs
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics (05-01) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Other character sums and Gauss sums (11T24) Inequalities involving eigenvalues and eigenvectors (15A42)
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.
- On the spectrum of an equitable quotient matrix and its application
- Decoherence and classicalization of continuous-time quantum walks on graphs
- Homogeneous coherent configurations from spherical buildings and other edge-coloured graphs
- Cut ratios and Laplacian eigenvalues
- Some results on the Laplacian spread conjecture
- Classification of vertices on social networks by multiple approaches
- Applications of graph spectra: an introduction to the literature
- Algebraic aspects of the normalized Laplacian
- Some applications of eigenvalues of graphs
- scientific article; zbMATH DE number 5841869 (Why is no real title available?)
- Spectral radius of graphs
- A NOTE ON NORMALISED HEAT DIFFUSION FOR GRAPHS
- An introduction to the theory of graph spectra
- Introduction to analysis on graphs
- Locating eigenvalues in graphs. Algorithms and applications
- Polaritons and excitons: Hamiltonian design for enhanced coherence
- Graphs and matrices
- Graph Spectra for Complex Networks
- Optimal functions with spectral constraints in hypercubes
- Laplace and Dirac operators on graphs
- Volume of Seifert representations for graph manifolds and their finite covers
- Spectra of graphs
- Eigenvalue bounds of the Kirchhoff Laplacian
- Introduction to spectral graph theory
- On the distance eigenvalues of design graphs
- Spectra of variants of distance matrices of graphs and digraphs: a survey
- Automorphism group of a family of distance-regular graphs which are not distance-transitive
- On a family of quasi-strongly regular Cayley graphs
- Minkowski \(\mathrm{t}\)-graph and Kendall \(\tau\)-graph of the symmetric group
- Universal graph series, chromatic functions, and their index theory
- Geometric planted matchings beyond the Gaussian model
- The distance spectrum of regular bipartite graphs of diameter 3
This page was built for publication: A brief introduction to spectral graph theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1643530)
