Take the 2-minute tour ×
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.

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

share|improve this question
1  
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
1  
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
1  
Dan's example of $C_3 \cup C_3$ and $C_6$ is not isospectral. –  Robert Israel Jan 22 '12 at 21:45
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Oh, interesting. I guess only the spectral radii need to be the same; extra structure may make the other eigenvalues of the graph irrelevant... –  Qiaochu Yuan Jan 22 '12 at 21:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.