[Nauty] Generating reduced graphs only?

Gordon Royle gordon at csse.uwa.edu.au
Wed Feb 9 23:43:01 EST 2005

> I think Gunnar is correct that you can't save much.  The only
> exception would be if you have some other parameters set so that
> non-reduced graphs are a much larger fraction.  Since the test

Indeed this is the case - I was not telling the full story to try to 
focus on the part causing problems, but ended up being misleading...

What I am actually doing is trying to use geng to generate graphs whose 
adjacency matrices have low rank -  there are other ways of doing this 
that are fairly efficient, but I want to see just how close I can get 
just using geng (or some other orderly algorithm if necessary).

So, I have a prune that eliminates a branch as soon as the rank gets 
too high...

The problem is that when I am generating the graphs of rank less than 
(for example) 6, I end up with every graph of ORDER up to 6 with every 
vertex replicated in every possible way... so that by the time the 
order gets to about 11, I am generating approximately 10^5 graphs for a 
few hundred reduced ones, and with each increase in order, the spurious 
graphs vastly outweigh the genuine examples.

This may kill the idea of using geng for this purpose, which is a 
reasonable outcome of the investigation, but I was wondering if there 
was something that I was missing in terms of earlier pruning...  for 
example, here is a basic question for which I don't even know the 
answer.. is it true that every reduced graph CAN be generated 
vertex-by-vertex with only reduced graphs as intermediates? Well, this 
is probably not true, but it is not immediate to me if there is a 
reduced graph such that every one-vertex deletion has a duplicate...



More information about the Nauty mailing list