This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000088 Number of graphs on n unlabeled nodes.
(Formerly M1253 N0479)
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)



Euler transform of the sequence A001349.

Also, number of equivalence classes of sign patterns of totally nonzero symmetric n X n matrices.


P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.

P. J. Cameron and C. R. Johnson, The number of equivalence patterns of symmetric sign patterns, Discr. Math., 306 (2006), 3074-3077.

R. L. Davis, The numbers of structures of finite relations, Proc. Amer. Math. Soc., 4 (1953), 486-494.

J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 519.

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.

S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.

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 498--500. 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): 5-21.

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.

A. Milicevic and N. Trinajstic, "Combinatorial Enumeration in Chemistry", Chem. Modell., Vol. 4, (2006), pp. 405-469.

W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.

M. Petkovsek and T. Pisanski, Counting disconnected structures: chemical trees, fullerenes, I-graphs and others, Croatica Chem. Acta, 78 (2005), 563-567.

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.

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.


Keith M. Briggs, Table of n, a(n) for n = 0..75 (From link below)

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, Single-qubit 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.

P. Butler and R. W. Robinson, On the computer calculation of the number of nonseparable graphs, pp. 191 - 208 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp. [Annotated scanned copy]

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

J. P. Dolch, Names of Hamiltonian graphs, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 259-271. (Annotated scanned copy of 3 pages)

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 105

E. Friedman, Illustration of small graphs

Harald Fripertinger, Graphs

Scott Garrabrant and Igor Pak, Pattern Avoidance is Not P-Recursive, preprint, 2015.

P. Hegarty, On the notion of balance in social network analysis, arXiv preprint arXiv:1212.4303, 2012.

S. Hougardy, Home Page

Vladeta Jovovic, Formulae for the number T(n,k) of n-multigraphs on k nodes

Maksim Karev, The space of framed chord diagrams as a Hopf module, arXiv preprint arXiv:1404.0026, 2014

J. M. Larson, Cheating Because They Can: Social Networks and Norm Violators, 2014. See Footnote 11.

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. [Annotated scanned copy]

Brendan McKay, Maple program (redirects to here.

G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

E. M. Palmer, Letter to N. J. A. Sloane, no date

Marko Riedel, Nonisomorphic graphs.

Sage, Common Graphs (Graph Generators)

S. S. Skiena, Generating graphs

N. J. A. Sloane, Illustration of initial terms

J. M. Tangen and N. J. A. Sloane, Correspondence, 1976-1976

S. Uijlen, B. Westerbaan, A Kochen-Specker system has at least 22 vectors, arXiv preprint arXiv:1412.8544 [cs.DM], 2014.

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


a(n) = 2^binomial(n, 2)/n!*(1+(n^2-n)/2^(n-1)+8*n!/(n-4)!*(3*n-7)*(3*n-9)/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*(3n-7)*2^{-2n}+64/3*n$4*(4n^2-34n+75)*2^{-3n}+O(n^8*2^{-4*n})] where n$k is the falling factorial: n$k=n(n-1)(n-2)...(n-k+1). - Keith Briggs (keith.briggs(AT)bt.com), Oct 24 2005

From David Pasino (davepasino(AT)yahoo.com), Jan 31 2009: (Start)

a(n) = a(n, 2), where a(n, t) is the number of t-uniform hypergraphs on n unlabeled nodes (cf. A000665 for t = 3 and A051240 for t = 4).

a(n, t) = Sum_{c : 1*c_1+2*c_2+...+n*c_n=n) per(c)*2^f(c), where:

..per(c) = 1/(Prod_{i=1..n} c_i!*i^c_i);

..f(c) = (1/ord(c)) * Sum_{r=1..ord(c)} Sum_{x : 1*x_1+2*x_2...+t*x_t=t} Product_{k=1..t} binomial(y(r, k; c), x_k);

..ord(c) = LCM{i : c_i>0};

..y(r, k; c) = Sum_{s|r : GCD(k, r/s)=1} s*c_(k*s) is the number of k-cycles of the r-th power of a permutation of type c.


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

a(n) = G(1) where G(z)= (1/n!) Sum_g det(I-g z^2)/det(I-g z) and g runs through the natural matrix n X n representation of the pair group A^2_n (for A^2_n see F. Harary and E. M. Palmer, Graphical Enumeration, page 83). - Leonid Bedratyuk, May 02 2015


# To produce all graphs on 4 nodes, for example (from N. J. A. Sloane, Oct 07 2013):


L:=[NonIsomorphicGraphs](4, output=graphs, outputform=adjacency):



Table[ NumberOfGraphs[n], {n, 0, 19}] (* Geoffrey Critzer, Mar 12 2011 *)



def a(n):

    return len(list(graphs(n)))

# Ralf Stephan, May 30 2014


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




N. J. A. Sloane


Harary gives an incorrect value for a(8); compare A007149



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 27 06:04 EDT 2016. Contains 273357 sequences.