[Nauty] Orbits partition refinement

[Dmitrii Tchekhovskoi]

Hello,

I'm a new member of this mailing list.

Unfortunately, I cannot prove or refute the following (7, below).
Can anybody help, please?

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')?

8. If yes, then how to prove it? If not or sometimes, how to build the smallest/simplest counterexample?


Thank you in advance.

Dmitrii

If I understand correctly, 5-6 closely resembles what nauty would do to G under certain circumstances.