[Nauty-list] Graph Isomorphism problem (a counter example)

Farid AmirGhiasvand ghiasvand at ut.ac.ir
Mon Sep 28 16:07:31 EST 2009


On 20/01/2009, at 7:35 AM,Mr. Abid Muslim Malik wrote:

> > 2) In order to check two graphs, you have to produce canonical  

> > labelling of each graph. If they are same then they are identical.  

> > right???

On Tue Jan 20 15:27:04 EST 2009  Mr. Prof Gordon Royle replied

 

> If the canonical labelling is the same then the graphs are isomorphic

 

 

 

Dear all,

 

I thought nauty computes Graph Isomorphism deterministically.

But during my works a found two graphs that are not isomorphic but when I use nauty program, I receive similar canonical labeling for those graphs.

I wrote below adjacency matrices of those graphs. As you can see in first graph, there is a vertex with degree of 1 (vertex no. 6) that is connected to a vertex with degree of 2 (vertex no. 4).

But in second graph there is not such vertex, so those graphs are not isomorphic. But nauty gives (0,0,0,0,0,0,0,1) for both of those.

I don’t know, may canonical labeling is only a unique descriptor for each automorphism group. 

Then if automorphism group of two graphs are same it is high probable that they are isomorphic !

Please let me know if you have any idea about this.

 

Thank you in advance for any help.

 

Farid AmirGhiasvand,

University Of Tehran

ghiasvand at ut.ac.ir

 

8

0 1 1 0 1 0 0 0 

1 0 1 1 0 0 0 0 

1 1 0 0 0 0 1 0 

0 1 0 0 0 1 0 0 

1 0 0 0 0 0 1 0 

0 0 0 1 0 0 0 0 

0 0 1 0 1 0 0 1 

0 0 0 0 0 0 1 0 

------------------------------------------------

8

0 1 0 1 1 0 0 0 

1 0 1 1 0 0 0 0 

0 1 0 0 0 1 1 0 

1 1 0 0 0 0 0 0 

1 0 0 0 0 0 1 0 

0 0 1 0 0 0 0 0 

0 0 1 0 1 0 0 1 

0 0 0 0 0 0 1 0 

------------------------------------------------

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20090928/e5fb677e/attachment.html 


More information about the Nauty mailing list