[Nauty] geng changes

[Brendan McKay]

* Sterten at aol.com <Sterten at aol.com> [021205 18:41]:
>  >
>  >There is no guarantee that all graphs smaller than the output
>  >size are generated, so this is invalid.
> 
> in practice it seems to work, so I used it for my counts:
> just copying the output to my counts-list.
> I found no counterexample so far.

Counterexamples definitely exist.  I'm not sure if there are
any with the classes you have made so far, but they might be.
You can see them already if you attempt to set the range of
degrees (-d and -D) or the number of edges.  For example,
geng -u -D3 10  (10-vertex graphs with maximum degree at most 3)
produces 330 intermediate graphs of order 9 but there are
actually 394 9-vertex graphs with maximum degree at most 3.

This behaviour will not change in later editions but may
become more pronounced dues to improvements in the algorithm.
 
> I wondered: what sorts of graphs are subgraphs of many(n) graphs
> and which of few ?

You can answer this asymptotically using the theory of random
graphs.  If H has m vertices, automorphism group order A and
e specified edges or non-edges, then a random labelled graph
on n vertices has on average  binomial(n,m)*(1/2)^e/A 
subgraphs isomorphic to H.  This also holds asymptotically
for unlabelled graphs.

Brendan.