[Nauty] Isomorphism test of labeled graphs

[Brendan McKay]

Hi.  Your mail was delayed (and might have been lost forever) because it
had the sender address akerlund at cs.helsinki.fi but you are subscribed to
the list as arto.akerlund at cs.helsinki.fi .  It has to be a perfect match.
(This is a Good Thing because it keeps out tons of spam messages.)

At
   http://cs.anu.edu.au/mailman/listinfo/nauty-list
you can unsubscribe/subscribe to fix the problem.  It is also ok to
subscribe with two different addresses.  You can mark one as
no-delivery so you don't get two copies of everything.

The answer to your question is that the two coloured graphs you
describe are non-isomorphic and nauty finds them non-isomorphic.

Generally speaking, if a graph is adorned with things attached to
the edges or vertices, such as colours, labels, tags, weights,
or whatever they are called, the word "isomorphism" usually implies
that vertices/edges are only mapped to vertices/edges with equal
adornments.  Nauty only knows about one type of adornment, namely
colours on the vertices.

Brendan.


* Arto J Akerlund, tkol <akerlund at cs.helsinki.fi> [041007 14:39]:
> 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]=0;   lab[1]=2;   lab[2]=1;  lab[3]=3;
> ptn[0]=1;   ptn[1]=0;   ptn[2]=1;  ptn[3]=0;
>   
> G2 :
>   0 :  1 3;
>   1 :  0 2;
>   2 :  1 3;
>   3 :  0 2;
> lab[0]=0;   lab[1]=1;   lab[2]=2;   lab[3]=3;
> ptn[0]=1;   ptn[1]=0;   ptn[2]=1;   ptn[3]=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.
> 
> _______________________________________________
> This is the nauty mailing list
> Post messages to nauty-list at cs.anu.edu.au
> nauty page: http://cs.anu.edu.au/~bdm/nauty/
> list page: http://cs.anu.edu.au/mailman/listinfo/nauty-list