[Nauty-list] Cheap accept in geng

[Brendan McKay]

Under the conditions of Lemma 2.25, all the cells of the partition
are orbits.  For the code in geng.c, the only question is whether
the cell containing the last vertex is an orbit, which is why
some cases of (number of cells) = n-5 can be included in addition
to what Lemma 2.25 has.

As for orbits on pairs of vertices, it seems to me that in all the
cases covered by Lemma 2.25, the orbit of an vertex pair depends
only on the cells containing the vertices and whether the vertex
pair is an edge or a non-edge. But don't take my word for it: there
are only a small number of graphs that may be the subgraph induced
by the union of the non-trivial cells, draw them all and look at
them (as I just did). The trivial cells are irrelevant.

If the conditions are relaxed further, things change. In your
example of a single 6-cell (not covered by Lemma 2.25), the cell
is indeed an orbit but the subgraph inside the cell might be the
triangular prism which has 2 distinct types of edge, or the hexagon
which has 2 distinct types of non-edge. But even here you can infer
the vertex pair orbits if you are prepared to look harder at the
subgraph inside the non-trivial cells.

Brendan.

* Christian Desrosiers <christian.desrosiers at polymtl.ca> [070419 08:01]:
> 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
> >
> 
> 
> 
> 
> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list