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

[Brendan McKay]

Hi,  I don't know what
    (0,0,0,0,0,0,0,1)
is in your mail.  Nauty does not produce any output like that.

In fact nauty finds these graphs to be non-isomorphic.

Perhaps if you gave more information..

Brendan.


* Farid AmirGhiasvand <ghiasvand at ut.ac.ir> [090928 16:08]:
> 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 
> 
> ------------------------------------------------
> 

> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list