Groupe d’études et de recherche en analyse des décisions

Spectral Reconstruction and Isomorphism of Graphs Using Variable Neighbourhood Search

Gilles Caporossi, Dragos Cvetkovic et Peter Rowlinson

The Euclidean distance between the eigenvalue sequences of graphs $$G$$ and $$H$$, on the same number of vertices, is called the spectral distance   between $$G$$ and $$H$$. This notion is the basis of a heuristic algorithm for reconstructing a graph with prescribed spectrum. By using a graph $$\Gamma$$ constructed from cospectral graphs $$G$$ and $$H$$, we can ensure that $$G$$ and $$H$$ are isomorphic if and only if the spectral distance between $$\Gamma$$ and $$G+K_2$$ is zero. This construction is exploited to design a heuristic algorithm for testing graph isomorphism. We present preliminary experimental results obtained by implementing these algorithms in conjunction with a meta-heuristic known as a variable neighbourhood search.

, 13 pages