

A000088


Number of graphs on n unlabeled nodes.
(Formerly M1253 N0479)


70



1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005168, 1018997864, 165091172592, 50502031367952, 29054155657235488, 31426485969804308768, 64001015704527557894928, 245935864153532932683719776, 1787577725145611700547878190848, 24637809253125004524383007491432768
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Euler transform of the sequence A001349.
Also, number of equivalence classes of sign patterns of totally nonzero symmetric n X n matrices.


REFERENCES

P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89102.
P. J. Cameron and C. R. Johnson, The number of equivalence patterns of symmetric sign patterns, Discr. Math., 306 (2006), 30743077.
R. L. Davis, The numbers of structures of finite relations, Proc. Amer. Math. Soc., 4 (1953), 486494.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 519.
F. Harary, Graph Theory. AddisonWesley, Reading, MA, 1969, p. 214.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 240.
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 25292571.
M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 54.
Lupanov, O. B. Asymptotic estimates of the number of graphs with n edges. (Russian) Dokl. Akad. Nauk SSSR 126 1959 498500. MR0109796 (22 #681).
Lupanov, O. B. "On asymptotic estimates of the number of graphs and networks with n edges." Problems of Cybemetics [in Russian], Moscow 4 (1960): 521.
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. 1422.
A. Milicevic and N. Trinajstic, "Combinatorial Enumeration in Chemistry", Chem. Modell., Vol. 4, (2006), pp. 405469.
W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 5378.
M. Petkovsek and T. Pisanski, Counting disconnected structures: chemical trees, fullerenes, Igraphs and others, Croatica Chem. Acta, 78 (2005), 563567.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
R. W. Robinson, Enumeration of nonseparable graphs, J. Combin. Theory 9 (1970), 327356.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Turner, James; Kautz, William H. A survey of progress in graph theory in the Soviet Union. SIAM Rev. 12 1970 suppl. iv+68 pp. MR0268074 (42 #2973). See p. 18.  N. J. A. Sloane, Apr 08 2014


LINKS

Keith M. Briggs, Table of n, a(n) for n = 0..75 (From link below)
J. M. Larson, Cheating Because They Can: Social Networks and Norm Violators, 2014. See Footnote 11.  N. J. A. Sloane, Mar 20 2014
R. Absil and H MÃ©lot, Digenes: genetic algorithms to discover conjectures about directed and undirected graphs, arXiv preprint arXiv:1304.7993, 2013
Natalie Arkus, Vinothan N. Manoharan, Michael P. Brenner. Deriving Finite Sphere Packings, Nov 24, 2010. (See Table 1.)
Benjamin A. Blumer, Michael S. Underwood and David L. Feder, Singlequbit unitary gates by graph scattering, arXiv:1111.5032, 2011
Keith M. Briggs, Combinatorial Graph Theory [Gives first 140 terms]
Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur and Hadrien Melot, House of Graphs: a database of interesting graphs, arXiv preprint arXiv:1204.3549, 2012.  From N. J. A. Sloane, Oct 08 2012
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 105
E. Friedman, Illustration of small graphs
Harald Fripertinger, Graphs
P. Hegarty, On the notion of balance in social network analysis, arXiv preprint arXiv:1212.4303, 2012.  From N. J. A. Sloane, Feb 02 2013
S. Hougardy, Home Page
Vladeta Jovovic, Formulae for the number T(n,k) of nmultigraphs on k nodes
Maksim Karev, The space of framed chord diagrams as a Hopf module, arXiv preprint arXiv:1404.0026, 2014
Brendan McKay, Maple program.
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
Marko Riedel, Nonisomorphic graphs.
Sage, Common Graphs (Graph Generators)
S. S. Skiena, Generating graphs
N. J. A. Sloane, Illustration of initial terms
Eric Weisstein's World of Mathematics, Simple Graph
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Degree Sequence
Index entries for "core" sequences


FORMULA

a(n)=2^binomial(n, 2)/n!*(1+(n^2n)/2^(n1)+8*n!/(n4)!*(3*n7)*(3*n9)/2^(2*n)+O(n^5/2^(5*n/2))) (see Harary, Palmer reference).  Vladeta Jovovic and Benoit Cloitre, Feb 01 2003
a(n)=2^binomial(n, 2)/n!*[1+2*n$2*2^{n}+8/3*n$3*(3n7)*2^{2n}+64/3*n$4*(4n^234n+75)*2^{3n}+O(n^8*2^{4*n})] where n$k is the falling factorial: n$k=n(n1)(n2)...(nk+1).  Keith Briggs (keith.briggs(AT)bt.com), Oct 24 2005
a(n) = a(n, 2) where a(n, t), the number of tuniform hypergraphs on n unlabeled nodes (cf. A000665 for t = 3 and A051240 for t = 4), is a(n, t) = (sum on c: 1*c_1+2*c_2+...+n*c_n= n) per(c)*2^f(c), where per(c) = 1/(prod on i=1 to n) c_i!*i^c_i and f(c) = (1/ord(c)) * (sum on r=1 to ord(c)) (sum on x: 1*x_1+2*x_2...+t*x_t=t) (prod on k = 1 to t) binom(y(r, k; c), x_k), where ord(c) = lcm{i : c_i > 0} and y(r, k; c) = (sum on sr with gcd(k, r/s) = 1) s*c_(k*s) (= the number of kcycles of the rth power of a permutation of type c).  David Pasino (davepasino(AT)yahoo.com), Jan 31 2009
a(n) ~ 2^binomial(n,2)/n! [see Flajolet and Sedgewick p. 106, Gross and Yellen, p. 519, etc.].  N. J. A. Sloane, Nov 11 2013
For asymptotics see also Lupanov 1959, 1960, also Turner and Kautz, p. 18.  N. J. A. Sloane, Apr 08 2014


MAPLE

# To produce all graphs on 4 nodes, for example (from N. J. A. Sloane, Oct 07 2013):
with(GraphTheory):
L:=[NonIsomorphicGraphs](4, output=graphs, outputform=adjacency):


MATHEMATICA

(* first do *) Needs["Combinatorica`"] (* then *) Table[ NumberOfGraphs[n], {n, 0, 19}] (* Geoffrey Critzer, Mar 12 2011 *)


PROG

(Sage)
def a(n):
return len(list(graphs(n)))
#  Ralf Stephan, May 30 2014


CROSSREFS

Partial sums of A002494.
Cf. A001349 (connected graphs), A002218, A006290. Second column of A063841. Row sums of A008406.
Sequence in context: A178944 A076320 A076321 * A071794 A234006 A107378
Adjacent sequences: A000085 A000086 A000087 * A000089 A000090 A000091


KEYWORD

core,nonn,nice


AUTHOR

N. J. A. Sloane.


EXTENSIONS

Harary gives an incorrect value for a(8). Compare A007149.


STATUS

approved



