Isomorphism of graphs with bounded eigenvalue multiplicity

TitleIsomorphism of graphs with bounded eigenvalue multiplicity
Publication TypeConference Papers
Year of Publication1982
AuthorsBabai L, Grigoryev Y.D, Mount D
Conference NameProceedings of the fourteenth annual ACM symposium on Theory of computing
Date Published1982///
Conference LocationNew York, NY, USA
ISBN Number0-89791-070-2

We investigate the connection between the spectrum of a graph, i.e. the eigenvalues of the adjacency matrix, and the complexity of testing isomorphism. In particular we describe two polynomial time algorithms which test isomorphism of undirected graphs whose eigenvalues have bounded multiplicity. If X and Y are graphs of eigenvalue multiplicity m, then the isomorphism of X and Y can be tested by an O(n4m+c) deterministic and by an O(n2m+c) Las Vegas algorithm, where n is the number of vertices of X and Y.