[Nauty] nauty colouring question

Brendan McKay bdm at cs.anu.edu.au
Tue Oct 7 01:41:02 EST 2003


The easiest way to do this is to augment the graph with m new vertices.
The i-th new vertex is joined to the i-th class of old vertex.  Now
apply an initial colouring with two colours: the old vertices have
one colour and the new vertices have the other colour.

Any automorphisms of the extended graph must be automorphisms of the
original graph, and must also map whole classes onto whole classes.
If I understand your question, this is what you want.

Brendan.


* Joost Winne <Joost.Winne at UGent.be> [031007 01:26]:
> 
> Say I have a graph with n = m*k vertices.
> I want to allow permutations inside any group of k vertices with labels
> (j*k, j*k + 1, ..., (j+1)*k - 1) for j in 0 <= j < m.
> 
> This would be easy by just setting lab[i] = i (0 <= i < n)
> and ptn[i] = 0 only if (i % k == k - 1).
> 
> But what if I would like to allow permutations of one k-pack to another
> k-pack as well ?
> 
> Say k = 3 and m = 2,
> then
> ------
> 0 -> 4
> 1 -> 3
> 2 -> 5
> ------
> 3 -> 0
> 4 -> 1
> 5 -> 2
> ------
> should be tested if it was an automorphism,
> but (0 3) should not be tested.
> 
> Is there a clever way to specify this to nauty or do I have to specify no
> initial colouring and then just look which automorphisms behave like the
> way I am interested in.
> 
> 
> _______________________________________________
> 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




More information about the Nauty mailing list