[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