[Nauty] geng changes
Brendan McKay
bdm at cs.anu.edu.au
Thu Dec 5 19:14:01 EST 2002
* 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.
More information about the Nauty
mailing list