[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