Spectral reconstruction and isomorphism of graphs using variable neighbourhood search

G. Caporossi, D. Cvetković, P. Rowlinson

The Euclidean distance between the eigenvalue sequences of graphs $G$ and $H$, on the same number of vertices, is called the {\em 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.