# [Nauty] Isomorphism test of labeled graphs

Arto J Akerlund, tkol akerlund at cs.helsinki.fi
Thu Oct 7 14:33:44 EST 2004

```Someone has asked something similar before and mr. McKay replied as
follows.

>Sorry, I somehow missed your message before.  In order for two labelled
>graphs to be isomorphic they must have the same number of vertices of
>each colour.  This is not tested by nauty!

>*If* the graphs have the same number of vertices of each colour, then
>you can test the graphs for isomorphism by finding the canonical graphs
>and comparing those.

>Incidentally, the values you put in ptn[] are examined for zero or
>non-zero only, so there is no point in using values other than 0 and 1
>(but it doesn't hurt either).

But what if the case was like this.

G1:

A-	-	-	-	B
|				|
|				|
B-	-	-	-	A

G2:

A-	-	-	-	A
|				|
|				|
B-	-	-	-	B

Data structures in nauty would thus be:

G1:
0 :  1 3;
1 :  0 2;
2 :  1 3;
3 :  0 2;
lab=0;   lab=2;   lab=1;  lab=3;
ptn=1;   ptn=0;   ptn=1;  ptn=0;

G2 :
0 :  1 3;
1 :  0 2;
2 :  1 3;
3 :  0 2;
lab=0;   lab=1;   lab=2;   lab=3;
ptn=1;   ptn=0;   ptn=1;   ptn=0;

Now there's an equal number of verticles of both colour and if G1 and G2
were unlabeled, they would be isomorphic. Is there a way to test
isomorphims for labeled graphs so that graphs G1 and G2 wouldn't be
isomorphic.

I'm not exactly sure what is the mathematical definition of 'isomorphism
of labeled graphs', but in my application G1 and G2 shouldn't be found
identical anyway.

```