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$?
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
|
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. |
|||
|
