Problems in spectral and extremal graph theory

Abstract

Spectral graph theory is the study of eigenvalues and eigenvectors of the matrices associated with graphs, such as the adjacency matrix, Laplacian, and signless Laplacian, to extract structural and combinatorial information of the underlying graph that is otherwise difficult to estimate. This thesis investigates several problems concerning the spectral radius, the second-largest eigenvalue, and the smallest eigenvalue of the adjacency matrices of graphs. ☐ A classical problem in spectral graph theory, posed by Brualdi and Solheid in 1986, asks to determine the maximum and minimum spectral radius of a graph within a given family of simple graphs. In Chapters 2, 3, and 4, we address this problem for different families of graphs. In particular, in Chapter 2, we study the minimum spectral radius of graphs of a given order and size, and we answer a question of Hong and another of Koolen in several cases. We show that if a graph attains the minimum spectral radius among all simple connected graphs of given order and size, then the difference between its maximum and minimum degree is at most 1. We also characterized the extremal graphs in all these cases. ☐ In Chapters 3 and 4, we study Turán-type problems for several complete multipartite graphs, generalizing a result of Erdős and Simonovits. As a consequence, we provide a solution to the Brualdi-Solheid problem for the family of connected graphs with a given order and dissociation number. Additionally, we extend our results to graphs with a given order and d-independence number. ☐ In Chapter 5, we study the second largest eigenvalue of regular graphs and address several instances of the spectral Moore problem, which asks for the maximum number of vertices in a k-regular graph whose second largest eigenvalue is at most θ < 2 √ k − 1. We also prove the non-existence of certain Moore polygons. ☐ Finally, in the last chapter, we study the smallest eigenvalue of regular graphs, generalizing a result of Aharoni, Alon, and Berger. As an application, we derive a lower bound on the smallest eigenvalue of the associahedron graph—the flip graph on triangulations of a convex n-gon.