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$?
Testing graph isomorphism with powers of the adjacency matrix
4
$\begingroup$
graph-theory
-
1The condition should imply that the two graphs are isospectral (http://en.wikipedia.org/wiki/Spectral_graph_theory#Isospectral_graphs), so I would look at known examples of isospectral but non-isomorphic graphs for counterexamples. – 2012-01-22
-
0@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$. – 2012-01-22
-
1Yes, I didn't say that the two conditions are equivalent, but I am still pretty sure any counterexample has to be isospectral. – 2012-01-22
-
1Dan's example of $C_3 \cup C_3$ and $C_6$ is not isospectral. – 2012-01-22
2 Answers
4
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.
3
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.
-
0Oh, interesting. I guess only the spectral radii need to be the same; extra structure may make the other eigenvalues of the graph irrelevant... – 2012-01-22