[Nauty] Orbits partition refinement
Dmitrii Tchekhovskoi
dmitrii at sysnet.net
Thu May 22 07:54:01 EST 2003
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.
More information about the Nauty
mailing list