[Nauty-list] Cheap accept in geng

Christian Desrosiers christian.desrosiers at polymtl.ca
Thu Apr 19 08:01:09 EST 2007


Hi,

If I understood correctly, when the cases of Lemma 2.25 are satisfied, the
equitable partition is the orbit partition, and therefore, the new vertex will
be maximum in regards to the canonical ordering.

Here is my question, and I apologize if it is not directly related to Nauty:

In the cases of Lemma 2.25, can the "vertex pair" orbit partition be inferred
easily (without having to call nauty) ? By "vertex pair" orbit partition, I
mean the pairs of vertices that are equivalent under automorphism ? The only
case that I can think of is when there is only one non-trivial cell of 6
vertices or less.

Thanks,

Christian

Selon Brendan McKay <bdm at cs.anu.edu.au>:

>
> 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