Is there research or are there results that discuss graph isomorphism in the context of spectral graph theory?Two known theorems of spectral graph theory are:Two graphs are called isospectral or cospectral if the adjacency matrices of the graphs have equal multisets of eigenvalues.Almost all trees are cospectral.The eigenvalues of a graph's adjacency matrix are invariant under relabeling (but this is not a necessary and sufficient condition).Furthermore, is graph isomorphism easy to solve?
Does spectral graph theory say anything about graph isomorphism
graph theory;linear algebra
Graph isomorphism has been mentioned along with primality testing as early as 1971 in Cook's famous paper on NP-completeness. Cook mentions that he was unable to prove the NP-completeness of both problems. Nowadays we known that primality testing is in P, but the status of graph isomorphism is still unknown. Most experts conjecture that it is NP-intermediate, that is, not in P but not NP-complete. Some conjecture that it should be solvable in quasipolynomial time (algorithms running in time $2^{\log^{O(1)} n}$). The best currently known algorithm, due to Luks, has running time $2^{O(\sqrt{n\log n})}$. It uses the so-called group theory method.The two most common approaches are individualization/refinement and the group theory method. The former approach tries to match vertices of one graph to vertices of the other. Given a vertex of degree $d$ belonging to the first graph, it can only be matches to a vertex of degree $d$ in the other graph, but this offers no saving if both graphs are $d$-regular. Individualization/refinement is a framework for generating more detailed types of vertices.It is possible that a similar approach can enhance the spectral method (which as stated fails for cospectral graphs), but I am not aware of any work along these lines (though it might exist; I'm not an expert in this area).The group theory method reduces graph isomorphism to the problem of finding generators for the automorphism groups of graphs. Given two graphs $G_1,G_2$, the idea is to compute generators for $\operatorname{Aut}(G_1 \cup G_2)$, and check whether any of them switches a vertex of $G_1$ with a vertex of $G_2$. For more details, see for example lecture notes of Arvind.For a recent overview of the state of the art, consult a paper by Babai; Babai is one of the principle researchers in the area.Practical graph isomorphism is a completely different issue. A recent overview can be found in a paper of McKay, author of the popular package nauty.