# Testing graph isomorphism with powers of the adjacency matrix

Suppose $A$ and $B$ are two square, symmetric, binary matrices with null diagonal representing the adjacency matrices of undirected graphs. If the multisets of the column-sums of $A$ and $B$ differ, then they are definitely not isomorphic. If the column-sum multisets are the same, then $A$ and $B$ might be isomorphic. Now I am wondering how the effectiveness of this test is improved by running it on $A^s$ and $B^s$ with a large integer $s$. Are there any two non-isomorphic graphs that "look" the same in this sense for all $s$ or even for an infinite number of values of $s$?

-
The condition should imply that the two graphs are isospectral (en.wikipedia.org/wiki/Spectral_graph_theory#Isospectral_graphs), so I would look at known examples of isospectral but non-isomorphic graphs for counterexamples. – Qiaochu Yuan Jan 22 '12 at 20:57
@Qiaochu, the article gives the examples $K_{1,4}$ and $C_4 \cup K_1$ but I don't think this is the same. $K_{1,4}$ has column-sum multiset $\{1,1,1,1,4\}$ and $C_4 \cup K_1$ has column-sum multiset $\{0,2,2,2,2\}$ so the test would correctly decide them to be non-isomorphic with $s=1$. – Dan Brumleve Jan 22 '12 at 21:02
Yes, I didn't say that the two conditions are equivalent, but I am still pretty sure any counterexample has to be isospectral. – Qiaochu Yuan Jan 22 '12 at 21:23
Dan's example of $C_3 \cup C_3$ and $C_6$ is not isospectral. – Robert Israel Jan 22 '12 at 21:45

Slightly more generally than Dan's example, if a graph is $r$-regular, the column-sum multiset of $A^s$ is $(r^s,\ldots,r^s)$. So any two nonisomorphic $r$-regular graphs on $n$ vertices provide an example.
If $A = C_3 \cup C_3$ and $B = C_6$, then it seems like the column-sum multiset is always $\{2^s,2^s,2^s,2^s,2^s,2^s\}$. I'm still interested in references and broader explanations.