[Nauty] geng changes

[Brendan McKay]

* Sterten at aol.com <Sterten at aol.com> [021206 18:59]:
> 
> Can't you include an option to do it ?
> E.g. n<0 ==> n=-n and all graphs 1..n are generated/counted.

This is better done as an external script since there is rarely
any efficiency gain.  The fact that it is hard to do this in a
long-obsolete system like DOS doesn't bother me.
 
> Also, can't you merge geng and countg, so we can use their
> features simultaneously ?

I follow the general Unix philosophy of well-defined pieces
rather than megalithic combinations.

>  >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.
> 
> hmm, symmetric subgraphs are less likely.
> 
> When I say subgraph, I usually mean vertex-induced subgraph.
> Then I assume it would be binomial(n,m)*2^(m*(1-m)/2)/A
> subgraphs isomorphic to H.

Yes.

> Estimating the ratio of H-free n-graphs is probably not so easy ?!

Very difficult in general.

Brendan.