[Nauty] Generating reduced graphs only?
Gordon Royle
gordon at csse.uwa.edu.au
Wed Feb 9 19:01:02 EST 2005
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?
Gordon
More information about the Nauty
mailing list