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
-
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