Spectral characterizations of graphs

Spectral graph theory studies the relation between structural properties of a graph and the eigenvalues of associated matrices. The spectrum (eigenvalues) contains a lot of information of the graph, but in general it does not determine it. Two graphs with the same spectrum for some type of matrix are called cospectral with respect to the corresponding matrix. Cospectral graphs help us understand “weaknesses” in identifying structures only using the spectrum. If a graph is not determined by the spectrum, this can be proved by constructing a nonisomorphic cospectral mate. The third chapter presents a new method to construct families of cospectral graphs that generalizes Godsil-McKay switching. For Godsil-McKay switching to work the graph needs a special structure. However, the presence of this structure does not imply that the graph is not determined by its spectrum; it may be that after switching the graph is isomorphic with the original one. Chapter four investigates this phenomenon, it shows some necessary conditions for isomorphism after switching and how they can be used to guarantee nonisomorphism after switching for some graph products. Chapter five shows how Godsil-McKay switching can be used to construct new strongly regular graphs with the same parameters as the symplectic graphs over the binary field, and it makes use of the 2-rank of the graph to prove nonisomorphism after switching. Chapter six gives a new contribution to the question: Can we see from the spectrum of a graph whether it is distance-regular?. Finally, chapter seven uses eigenvalue interlacing to obtain bounds for the sums of Laplacian eigenvalues of graphs, and characterize the case of equality. As a consequence, inequalities involving bounds for some well-known parameters of a graph are shown.