[Nauty-list] Cheap accept in geng

Brendan McKay bdm at cs.anu.edu.au
Wed Apr 11 12:40:07 EST 2007


Hi, This is Lemma 2.25 of Practical Graph Isomorphism, available at
http://cs.anu.edu.au/~bdm/papers/pgi.pdf .

However the proof is not given there. 

The idea is that for some shapes of equitable partitions on a simple
graph, there must be a subgroup of the automorphism group whose
orbits are the same as the cells of the partition.

In the case of only a small number of vertices not in a cell of size
1, the proof consists of considering all the possible ways those
cells can be joined to themselves and each other. For example, if
there is just nontrivial cell and it has size 4, then inside that
cell there must be one of the regular graphs of order 4 (which are
all vertex-transitive), and any vertex outside that cell must be
adjacent to all or none of it. So the graph has an automorphism
which consists of a cycle of length 4 moving that cell around.

In geng.c, the gain is that some vertices are inferred to be
equivalent under the group without applying nauty.

Brendan.

* Christian Desrosiers <christian.desrosiers at polymtl.ca> [070410 23:30]:
> Hello everyone,
> 
> I'm trying to figure out the cheap accept rules of function accept2, without
> success. For instance, why does it accept a graph G if the refined partition of
> V(G) has a number of cells greater than |V(G)|-4 ? Same question for the other
> cases. Is this something that was determined empirically, or can it be
> explained simply ?
> 
> Thanks in advance,
> 
> Christian Desrosiers
> 
> 
> 
> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list




More information about the Nauty mailing list