[Nauty-list] Canonization of a vertex-subset possible?

coxalan at web.de coxalan at web.de
Fri Mar 9 19:23:25 EST 2007


Hello,

thanks for nauty, it is a great program.

I understand that it can canonize a graph with respect to its automorphism group.
Now I want to canonize a subset of the vertices of a graph with respect to the authomorphisms of the full graph.

For the case that my formulation is unclear, an easy example:
Consider the complete bipartite graph G = K_{2,2}:

1---3
 \ /
  X
 / \
2---4

Now I choose the vertex-subset {1,4}. A canonized form of this subset with respect to the automorphisms of the graph G would be one of the sets {1,3},{1,4},{2,3},{2,4}, but not {1,2} or {3,4}.

Is it possible to compute such a canonized form with nauty?
_________________________________________________________________________
In 5 Schritten zur eigenen Homepage. Jetzt Domain sichern und gestalten! 
Nur 3,99 EUR/Monat! http://www.maildomain.web.de/?mc=021114





More information about the Nauty mailing list