Construction of Isospectral Graphs
Presented by Mr. Mario THUENE
Type: Oral presentation
Track: Graph Spectra and its Applications
Isospectrality is a recurring theme in graph theory. Several constructions are known for pairs of graphs that are non isomorphic but have the same spectrum. Those often only work for one or a few particular graph matrices. One of the most famous examples was given by Godsil/McKay. Using edge switching their classical method produces graphs that are isospectral w.r.t. both the adjacency matrix and the adjacency matrix of the complement but usually not w.r.t. the normalized Laplacian. The talk will give an easy construction for non regular graphs which are isospectral w.r.t. a large family of algebraic graph matrices including the adjacency matrix, the complement, the Seidel matrix, the (ordinary, signless and normalized) Laplacian and several others. This new method makes no explicit use of edge switching.