Constructing Cospectral Graphs using Partitioned Tensor Product

Abstract

The goal in Spectral Graph Theory is to understand the structure of a graph using the spectrum of its associated matrices. This MS thesis is a contribution to the study of constructions of cospectral nonisomorphic graphs. We first generalize a construction based on partitioned tensor product introduced by Godsil and Mckay and discuss its particular cases. Then, we use the idea of taking partitioned tensor products to obtain new cospectral constructions from the existing ones. We also generalize the unfolding operation on the bipartite graph introduced by Butler, obtain its modifications, as well as introduce the notion of unfolding a multipartite graph to obtain cospectral nonisomorphic graphs.