[Nauty] counting graphs

Sterten at aol.com Sterten at aol.com
Wed Dec 4 21:26:02 EST 2002


geng needs 10 years to count graphs of size 13. See geng.c

On  http://cs.anu.edu.au/~bdm/data/graphcounts.txt
Brendan gives graph-counts upto size 16.
 " Counts of unlabelled simple graphs.  For each n, a table of values
   (edges, connected graphs, all graphs) is given.  Computed using Maple
   by Brendan McKay <bdm at cs.anu.edu.au> with help from Gordon Royle. "

The EIS gives graph-counts upto size 19 , see below.

So, apparently there are better methods to count graphs than geng.
What methods are these ?


Guenter.



Reply from On-Line Encyclopedia 
Greetings from the On-Line Encyclopedia of Integer Sequences!
Here is Sequence A000088 (this will take a moment): 
ID Number: A000088 (Formerly M1253 and N0479)
Sequence:  1,1,2,4,11,34,156,1044,12346,274668,12005168,1018997864,
           165091172592,50502031367952,29054155657235488,
           31426485969804308768,64001015704527557894928,
           245935864153532932683719776,1787577725145611700547878190848,
           24637809253125004524383007491432768
Name:      Graphs with n nodes.
References P. J. Cameron, Some sequences of integers, Discrete Math., 75 
(1989),
              89-102.
           F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.
           F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 
NY,
              1973, p. 240.
           M. D. McIlroy, Calculation of numbers of structures of relations on
              finite sets, Massachusetts Institute of Technology, Research
              Laboratory of Electronics, Quarterly Progress Reports, No. 17, 
Sep.
              15, 1955, pp. 14-22.
           W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen,
              Math. Ann., 174 (1967), 53-78.
           R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
           R. W. Robinson, Enumeration of non-separable graphs, J. Combin.
              Theory 9 (1970), 327-356.
Links:     P. J. Cameron, Sequences realized by oligomorphic permutation 
groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
           E. Friedman, Illustration of small graphs
           Harald Fripertinger, Graphs
           Vladeta Jovovic, Formulae for the number T(n,k) of n-multigraphs 
on k nodes
           S. S. Skiena, Generating graphs
           N. J. A. Sloane, Illustration of initial terms
           Index entries for "core" sequences
           E. W. Weisstein, Simple Graph
           E. W. Weisstein, Connected Graph
           E. W. Weisstein, Degree Sequence
See also:  Cf. A001349, A002218, A006290. A row of A063841.
Keywords:  core,nonn,nice
Offset:    0
Author(s): njas
Extension: Harary gives an incorrect value for a(8). Compare A007149.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20021204/795d0e34/attachment.html 


More information about the Nauty mailing list