A study of eigenspaces of graphs (Q2365658)

The relationship between the structure of a graph and its eigenspaces is investigated. Most emphasis is given to the angles between the eigenspaces and the vectors of the standard basis in \(\mathbb{R}^ n\). It is shown that for any given graph one can define particular bases of its eigenspaces, called canonical bases, in such a way that two graphs are isomorphic if and only if they have the same spectrum and the same canonical bases. Unfortunately, it is not clear if one can use these results to devise an efficient algorithm for isomorphism checking. It is also not clear to what extent these results are related to the polynomial time algorithm for isomorphisms of graphs with bounded eigenvalue multiplicities of Babai, Grigorjev, and Mount.