[Nauty] Generating reduced graphs only?

[Gunnar Brinkmann]

Hi Gordon,

You wrote

> Suppose that for various computations, I am only interested in REDUCED
> graphs - that is, no two vertices can have identical neighbourhoods...
>
> Obviously I can generate everything and then throw away those with
> vertices with identical neighbourhoods at the end...  equally clearly,
> I wish to do better than this, by pruning (using geng's "prune"
> facility) those that will necessarily end up as not reduced.
>
> If I am aiming at n vertices, then at the final step, the n-1 vertex
> graph can have two vertices with identical neighbourhoods, provided the
> final step makes the final vertex adjacent to just one of those two.
> However, it can't have THREE vertices with identical neighbourhoods
> because then no matter what I do, the final step will leave two of them
> identical...
>
> Similarly when I have n-i vertices, I cannot have more than 2^i
> vertices with identical neighbourhoods...
>
> But can I do better?

Well, simply asking: Does it play any role? Why do you want to do
better than throwing away those with identical neighbouhoods. They are
clearly a subset of those with nontrivial automorphism group, so you
will generate almost all graphs anyway. The only thing that really
increases efficiency is that you want to avoid testing on the highest
level and that is already done by what you propose: Make sure on level
n-1 that there are no 3 vertices with the same neighbourhood and that
in every pair of vertices with the same neighbourhood exactly one is
the neighbour of the new one. Furthermore make sure that the new
vertex isn't a double of another.

I don't think that even earlier bounding criteria will have any effect on
the efficiency -- the efficiency just depends on how efficiently you
implement the steps above... Or do I miss something?


						Gunnar