[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