[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