[Nauty] Re: Orbits partition refinement

Dmitrii Tchekhovskoi dmitrii at sysnet.net
Fri May 23 08:01:01 EST 2003


Brendan,

Thank you.

I would be quite interested to get a look and feel of the counterexample.

I was trying to use these sequential refinements (with a hard to predict next vertex selection) of initially orbit-partitioned colored graph wrt a vertex to eventually map the graph onto itself.
 
The purpose was, for example, to optimize the arrangement of additional labels sitting on vertices vs previously found canonical numbering.

If counterexamples may be so simple that they can be found among feasible chemical graphs then I probably have to switch to Jerrum's representation of a perm group and a base change.

Regards

Dmitrii



>> Suppose:
>> 
>> 1. G is a colored simple graph;
>> 2. G has N vertex orbits under Aut(G);
>> 3. Vertices in the ith orbit have same color = i (i=1,...,N);
>> 4. Vertex v of G belongs to an orbit that has more than one vertex;
>> 5. Graph G' is made out of G by changing color of v to a new color = N+1.
>> 6. A refinement procedure applied to G' produced coarsest equitable partition P'.
>> 
>> Questions:
>> 
>> 7. Is P' the orbits partition of G' under Aut(G')?
>
>Not necessarily.
> 
>> 8. If yes, then how to prove it? If not or sometimes, how to build the smallest/simplest counterexample?
>
>Good question.  I know there are examples where the whole group Aut(G)
>is transitive, but the refinement wrt one vertex is coarser than the
>orbits of the stabiliser.  Maybe Gordon has one in his head already;
>I'll have to think about it.
> 
>> If I understand correctly, 5-6 closely resembles what nauty would do to G under certain circumstances.
>
>Right.  If refinement always gave orbits then nauty would run in 
>polynomial time, but life is not so kind.
>
>Brendan.
> 





More information about the Nauty mailing list