A Combinatorial Analysis of the Eigenvalues of the Laplacian Matrices of Cographs

Abstract

Cographs, also known as complement reducible graphs or decomposable graphs, are a recursively defined class of graphs built from a single vertex by the operations of disjoint union and join. The eigenvalues of a cograph's Laplacian matrix are nonnegative integers. In this thesis, we explore the combinatorial significance of cograph Laplacian eigenvalues. We show that the second smallest-eigenvalue of a cograph C, also known as the algebraic connectivity of C, is equal to the vertex connectivity of C. We give necessary and sufficient conditions for the second-smallest eigenvalue to be unique, and provide a characterization of the Fiedler vector when the second-smallest eigenvalue is unique. Finally, we give a relationship between the nonzero eigenvalues of C and the twin numbers of C, generalizing a result due to Merris stating that the nonzero eigenvalues of a threshold graph T are equal to the Ferrer's conjugate of the degree sequence of T.