# [Nauty-list] graph isomorphism

Gordon Royle gordon at maths.uwa.edu.au
Wed Feb 18 12:19:30 EST 2009

```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...

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

> 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

```