Contributions in Algebraic Graph Theory
2026-07-20 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors explore two main topics in algebraic graph theory focused on using spectra, which are lists of special numbers associated with graphs. First, they study when a graph can be uniquely identified just by these spectral numbers, proving new results for certain important types of graphs and introducing a new family called graphs of pyramids. Second, they analyze a special kind of graphs called generalized-Hamming graphs to understand their symmetry properties, using various mathematical techniques. Their work also gives exact formulas for a graph property called the Lovász theta function when these graphs or their complements have specific symmetrical features.
spectral graph theoryadjacency spectrumLaplacian matrixstrongly regular graphsCauchy's interlacing theoremSchur complementsgeneralized-Hamming graphsedge-transitive graphsassociation schemesLovász theta function
Authors
Noam Krupnik
Abstract
This thesis investigates two central directions in algebraic graph theory, with an emphasis on spectral methods: spectral determination of graphs and transitivity properties of generalized-Hamming graphs and their complements. The first part focuses on graphs that are determined by the spectra of associated matrices. We study spectral determination with respect to the adjacency, Laplacian, signless Laplacian, and normalized Laplacian matrices, with particular emphasis on the adjacency spectrum. We survey existing results on graphs determined by their spectrum and develop new proof techniques for establishing spectral uniqueness. In particular, we present new proofs for the spectral characterization of complete bipartite graphs and Turán graphs, as well as some new results related to the spectral characterization of the important family of strongly regular graphs. In addition, we introduce a new family of graphs, called \emph{the graphs of pyramids}, and prove that they are determined by their adjacency spectrum using tools from matrix analysis, such as Cauchy's interlacing theorem and Schur complements. The second part of the thesis studies generalized-Hamming graphs, a family of Cayley graphs that generalize the sub-family of Hamming graphs, and their complements. We classify the parameters for which these graphs are edge-transitive or even distance-transitive. Our analysis combines spectral methods, group-theoretic arguments, and techniques from the theory of association schemes. As an application, we derive closed-form expressions for the Lovász $\vartheta$-function of generalized-Hamming graphs and their complements whenever either the graph or its complement is edge-transitive. Overall, the results demonstrate how spectral methods provide powerful tools for understanding the structure and symmetry of graphs, and they suggest several directions for further research.