[Nauty-list] Custom pruning in genbg

[Brendan McKay]

* Stephen Hartke <hartke at gmail.com> [110805 03:38]:
> 
> Would it be possible to maintain connected?  It seems to me that this would
> be possible if a cut vertex is never the canonical vertex to delete.  Does
> geng operate in this way when generating connected graphs, or does it filter
> afterward?

Yes, it is possible, but geng is not written in a way to make that
easy. It is rather deeply imbedded in geng that the last vertex
added has the largest degree. Now imagine that the unique vertex
of largest degree is a cut-vertex. The program could be written to
use instead the non-cut vertex of largest degree, but that would be
less efficient in most graph classes. Geng uses a bit of look-ahead
combined with a filter at the end.

> > Nauty doesn't always generate all the graphs up to order n in
> > the process of making those of order n, but usually it makes a
> > large fraction of them.
>
> Could you please explain this a bit more? My understanding was
> that all of the smaller graphs were generated.

For example, to make the n-vertex graphs of maximum degree 3, it
is not necessary to make the cubic graphs of order n-1.  This is
another consequence of the largest degree rule I mentioned above.

Brendan.