Spectral reconstruction and isomorphism of graphs using variable neighbourhood search

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

Bulletin de l'Académie serbe des sciences. Classe des sciences mathématiques et naturelles, Tome 39 (2014) no. 1

Résumé

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.