New constructions of nonregular cospectral graphs

Abstract

We consider two types of joins of graphs G1{G}_{1} and G2{G}_{2}, G1⊻G2{G}_{1}\hspace{0.33em}⊻\hspace{0.33em}{G}_{2} – the neighbors splitting join and G1∨=G2{G}_{1}\mathop{\vee }\limits_{=}{G}_{2} – the nonneighbors splitting join, and compute the adjacency characteristic polynomial, the Laplacian characteristic polynomial, and the signless Laplacian characteristic polynomial of these joins. When G1{G}_{1} and G2{G}_{2} are regular, we compute the adjacency spectrum, the Laplacian spectrum, the signless Laplacian spectrum of G1∨=G2{G}_{1}\mathop{\vee }\limits_{=}{G}_{2}, and the normalized Laplacian spectrum of G1⊻G2{G}_{1}\hspace{0.33em}⊻\hspace{0.33em}{G}_{2} and G1∨=G2{G}_{1}\mathop{\vee }\limits_{=}{G}_{2}. We use these results to construct nonregular, nonisomorphic graphs that are cospectral with respect to the four matrices: adjacency, Laplacian, signless Laplacian and normalized Laplacian.

Keywords

• spectra of graphs
• nonisomorphic cospectral graphs
• ns and nns joins
• coronal and schur complement
• 05c50