Wang-Qiu-Hu switching and isomorphism

Abstract

Cospectral graphs (graphs that share the same eigenvalues) expose the limitations of using the graph spectrum to identify graphs uniquely, and they help clarify which structural properties a graph spectrum cannot capture. Switching methods, which are standard tools for constructing cospectral graphs, require specific structural and algebraic conditions in order to preserve the graph spectrum, but the switched graph need not be non-isomorphic to the original graph. This paper studies the isomorphism problem for a recent and prolific adjacency-spectrum switching method: Wang-Qiu-Hu (WQH) switching. Common-neighbour multisets associated with a WQH partition are used to derive an external common-neighbour criterion for certifying non-isomorphism after WQH-switching. The criterion is applied to clique extensions and weak tensor products, with coclique extensions as a special case. These applications yield infinite families of cospectral non-isomorphic graphs, including some known constructions. Finally, the conditions of WQH-switching are extended to generalized adjacency matrices and, under an additional degree condition, to Laplacian and signless Laplacian matrices.