[Nauty] geng changes
Sterten at aol.com
Sterten at aol.com
Fri Dec 6 18:59:03 EST 2002
Brendan wrote:
>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.
I have 1106 and 1165.
This resolves, when I include the D3 checking into my
PRUNE subroutine instead of using the -D3 switch.
However I can't do it with e.g. connected graphs -c switch.
Since time(n) is only a small fraction of time(n+1),
I could call 1..n consecutively and then display all results.
But I can't modify geng.c easily to do it, so I use a Basic-program
to call geng.exe n times, but I can't redirect output in DOS
since you print to stderr, so I'll grap the screen-buffer...
Can't you include an option to do it ?
E.g. n<0 ==> n=-n and all graphs 1..n are generated/counted.
Also, can't you merge geng and countg, so we can use their
features simultaneously ?
>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.
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.
Estimating the ratio of H-free n-graphs is probably not so easy ?!
Guenter.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20021206/2b0da3e3/attachment.html
More information about the Nauty
mailing list