[Nauty-list] graph isomorphism

[Gordon Royle]

On 18/02/2009, at 9:51 AM, Sara Voss wrote:

> Is there a way for Nauty to find the following two graphs isomorphic?
>
> graph 1          graph2
> 0 = 1             0 = 1
> ||     ||             ||    ||
> 2 = 3             3 = 2
>
> Nauty produces different canonical labellings for these graphs.  I'm

It shouldn't...

Here is a "dreadnaut" run with some comments...


(1) Start up dreadnaut and enter the graph, use "t" to type it out

Dreadnaut version 2.4 (32 bits).
 > n=4
 > g
  0 : 1 2;
  1 : 3;
  2 : 3.
 > t
   0 :  1 2;
   1 :  0 3;
   2 :  0 3;
   3 :  1 2;

(2) Turn on "canonical labelling", then run nauty, then print the  
"canonically labelled graph"

 > c
 > x
(1 2)
level 2:  3 orbits; 1 fixed; index 2
(0 1)(2 3)
level 1:  1 orbit; 0 fixed; index 4
1 orbit; grpsize=8; 2 gens; 6 nodes; maxlev=3
tctotal=8; canupdates=1; cpu time = 0.00 seconds
 > b
  0 1 2 3
   0 :  1 2;
   1 :  0 3;
   2 :  0 3;
   3 :  1 2;

Note that the labelling required (the line 0 1 2 3)  is the identity  
so the canonically labelled graph is the same as the original.



(3) Enter the second graph, run nauty and type the canonically  
labelled graph

 > g
  0 : 1 3;
  1 : 2;
  2 : 3.
 > t
   0 :  1 3;
   1 :  0 2;
   2 :  1 3;
   3 :  0 2;
 > x
(1 3)
level 2:  3 orbits; 1 fixed; index 2
(0 1)(2 3)
level 1:  1 orbit; 0 fixed; index 4
1 orbit; grpsize=8; 2 gens; 6 nodes; maxlev=3
tctotal=8; canupdates=1; cpu time = 0.00 seconds
 > b
  0 1 3 2
   0 :  1 2;
   1 :  0 3;
   2 :  0 3;
   3 :  1 2;

This time the permutation required is 0 1 3 2 and so the canonically  
labelled graph is NOT the initial graph but in fact equal to the first  
graph.



Gordon