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)

%I M1253 N0479

%S 1,1,2,4,11,34,156,1044,12346,274668,12005168,1018997864,165091172592,

%T 50502031367952,29054155657235488,31426485969804308768,

%U 64001015704527557894928,245935864153532932683719776,1787577725145611700547878190848,24637809253125004524383007491432768

%N Number of graphs on n unlabeled nodes.

%C Euler transform of the sequence A001349.

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

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

%D F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.

%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 240.

%D Thomas Boyer-Kassem, Conor Mayo-Wilson, Scientific Collaboration and Collective Knowledge: New Essays, New York, Oxford University Press, 2018, see page 47.

%D M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 54.

%D 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).

%D Lupanov, O. B. "On asymptotic estimates of the number of graphs and networks with n edges." Problems of Cybernetics [in Russian], Moscow 4 (1960): 5-21.

%D 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.

%D R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.

%D R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Keith M. Briggs, <a href="/A000088/b000088.txt">Table of n, a(n) for n = 0..75</a> (From link below)

%H R. Absil and H. Mélot, <a href="http://arxiv.org/abs/1304.7993">Digenes: genetic algorithms to discover conjectures about directed and undirected graphs</a>, arXiv preprint arXiv:1304.7993 [cs.DM], 2013.

%H Natalie Arkus, Vinothan N. Manoharan, Michael P. Brenner. <a href="http://arxiv.org/abs/1011.5412"> Deriving Finite Sphere Packings</a>, arXiv:1011.5412 [cond-mat.soft], Nov 24, 2010. (See Table 1.)

%H Leonid Bedratyuk and Anna Bedratyuk, <a href="http://www.proceedings.bas.bg/cgi-bin/mitko/0DOC_abs.pl?2016_3_02">A new formula for the generating function of the numbers of simple graphs</a>, Comptes rendus de l’Académie Bulgare des Sciences, Tome 69, No 3, 2016, p.259-268

%H Benjamin A. Blumer, Michael S. Underwood and David L. Feder, <a href="http://arxiv.org/abs/1111.5032">Single-qubit unitary gates by graph scattering</a>, arXiv:1111.5032 [quant-ph], 2011.

%H Keith M. Briggs, <a href="http://keithbriggs.info/cgt.html">Combinatorial Graph Theory</a> [Gives first 140 terms]

%H Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur and Hadrien Melot, <a href="http://arxiv.org/abs/1204.3549">House of Graphs: a database of interesting graphs</a>, arXiv preprint arXiv:1204.3549 [math.CO], 2012.

%H P. Butler and R. W. Robinson, <a href="/A002218/a002218.pdf">On the computer calculation of the number of nonseparable graphs</a>, 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]

%H P. J. Cameron, <a href="http://dx.doi.org/10.1016/0012-365X(89)90081-2">Some sequences of integers</a>, Discrete Math., 75 (1989), 89-102.

%H P. J. Cameron, <a href="http://dx.doi.org/10.1016/S0167-5060(08)70569-7">Some sequences of integers</a>, in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.

%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

%H P. J. Cameron and C. R. Johnson, <a href="http://dx.doi.org/10.1016/j.disc.2004.10.029">The number of equivalence patterns of symmetric sign patterns</a>, Discr. Math., 306 (2006), 3074-3077.

%H Gi-Sang Cheon, Jinha Kim, Minki Kim, Sergey Kitaev, <a href="https://arxiv.org/abs/1803.01055">On k-11-representable graphs</a>, arXiv:1803.01055 [math.CO], 2018.

%H R. L. Davis, <a href="http://dx.doi.org/10.1090/S0002-9939-1953-0055294-2">The number of structures of finite relations</a>, Proc. Amer. Math. Soc. 4 (1953), 486-495.

%H J. P. Dolch, <a href="/A001349/a001349.pdf">Names of Hamiltonian graphs</a>, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 259-271. (Annotated scanned copy of 3 pages)

%H D. S. Dummit, E. P. Dummit, H. Kisilevsky, <a href="http://arxiv.org/abs/1512.06480">Characterizations of quadratic, cubic, and quartic residue matrices</a>, arXiv preprint arXiv:1512.06480 [math.NT], 2015.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html">Analytic Combinatorics</a>, 2009; see page 105

%H E. Friedman, <a href="/A000088/a000088a.gif">Illustration of small graphs</a>

%H Harald Fripertinger, <a href="http://www.mathe2.uni-bayreuth.de/frib/html/book/hyl00_41.html">Graphs</a>

%H Scott Garrabrant and Igor Pak, <a href="http://www.math.ucla.edu/~pak/papers/PatternAvoid10.pdf">Pattern Avoidance is Not P-Recursive</a>, preprint, 2015.

%H P. Hegarty, <a href="http://arxiv.org/abs/1212.4303">On the notion of balance in social network analysis</a>, arXiv preprint arXiv:1212.4303 [cs.SI], 2012.

%H S. Hougardy, <a href="http://www.or.uni-bonn.de/~hougardy/">Home Page</a>

%H S. Hougardy, <a href="http://dx.doi.org/10.1016/j.disc.2006.05.021">Classes of perfect graphs</a>, Discr. Math. 306 (2006), 2529-2571.

%H A. Itzhakov, M. Codish, <a href="http://arxiv.org/abs/1511.08205">Breaking Symmetries in Graph Search with Canonizing Sets</a>, arXiv preprint arXiv:1511.08205 [cs.AI], 2015-2016.

%H Dan-Marian Joiţa, Lorentz Jäntschi, <a href="https://doi.org/10.3390/math5040084">Extending the Characteristic Polynomial for Characterization of C_20 Fullerene Congeners</a>, Mathematics (2017), 5(4), 84.

%H Vladeta Jovovic, <a href="/A063843/a063843.rtf">Formulae for the number T(n,k) of n-multigraphs on k nodes</a>

%H Maksim Karev, <a href="http://arxiv.org/abs/1404.0026">The space of framed chord diagrams as a Hopf module</a>, arXiv preprint arXiv:1404.0026 [math.GT], 2014.

%H J. M. Larson, <a href="https://www.sas.upenn.edu/polisci/sites/www.sas.upenn.edu.polisci/files/Larson_cheaters_Feb2014.pdf">Cheating Because They Can: Social Networks and Norm Violators</a>, 2014. See Footnote 11.

%H Steffen Lauritzen, Alessandro Rinaldo, Kayvan Sadeghi, <a href="https://arxiv.org/abs/1709.03885">On Exchangeability in Network Models</a>, arXiv:1709.03885 [math.ST] 2017.

%H M. D. McIlroy, <a href="/A000088/a000088.pdf">Calculation of numbers of structures of relations on finite sets</a>, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 14-22. [Annotated scanned copy]

%H B. D. McKay, <a href="http://www.csse.uwa.edu.au/~gordon/remote/graphs/graphcount">Maple program</a> (redirects to <a href="http://staffhome.ecm.uwa.edu.au/~00013890/remote/graphs/graphcount">here</a>.

%H B. D. McKay, <a href="/A000088/a000088_1.txt">Maple program</a> [Cached copy, with permission]

%H B. D. McKay, <a href="http://users.cecs.anu.edu.au/~bdm/data/graphs.html">Simple graphs</a>

%H A. Milicevic and N. Trinajstic, <a href="http://www.sicmm.org/~FAMNIT-knjiga/wwwANG/web-pages/405_469_tcm18-67839%5B1%5D.pdf">Combinatorial Enumeration in Chemistry</a>, Chem. Modell., Vol. 4, (2006), pp. 405-469.

%H W. Oberschelp, <a href="http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002298732">Kombinatorische Anzahlbestimmungen in Relationen</a>, Math. Ann., 174 (1967), 53-78.

%H M. Petkovsek and T. Pisanski, <a href="http://hrcak.srce.hr/file/4232">Counting disconnected structures: chemical trees, fullerenes, I-graphs and others</a>, Croatica Chem. Acta, 78 (2005), 563-567.

%H G. Pfeiffer, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.html">Counting Transitive Relations</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

%H E. M. Palmer, <a href="/A000088/a000088_EMP.pdf">Letter to N. J. A. Sloane, no date</a>

%H Marko Riedel, <a href="http://www.roard.com/docs/cookbook/cbsu5.html#x8-170001.5">Nonisomorphic graphs</a>.

%H R. W. Robinson, <a href="http://dx.doi.org/10.1016/S0021-9800(70)80089-8">Enumeration of non-separable graphs</a>, J. Combin. Theory 9 (1970), 327-356.

%H Sage, <a href="http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_generators.html">Common Graphs (Graph Generators)</a>

%H S. S. Skiena, <a href="http://www.cs.sunysb.edu/~algorith/files/generating-graphs.shtml">Generating graphs</a>

%H N. J. A. Sloane, <a href="/A000088/a000088.gif">Illustration of initial terms</a>

%H P. R. Stein, <a href="/A004250/a004250.pdf">On the number of graphical partitions</a>, pp. 671-684 of Proc. 9th S-E Conf. Combinatorics, Graph Theory, Computing, Congr. Numer. 21 (1978). [Annotated scanned copy]

%H Peter Steinbach, <a href="/A000088/a000088.txt">Field Guide to Simple Graphs, Volume 1</a>, Overview of the 17 Parts (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

%H Peter Steinbach, <a href="/A000088/a000088_1.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 1

%H Peter Steinbach, <a href="/A000088/a000088_2.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 2

%H Peter Steinbach, <a href="/A000088/a000088_3.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 3

%H Peter Steinbach, <a href="/A000088/a000088_4.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 4

%H Peter Steinbach, <a href="/A000088/a000088_5.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 5

%H Peter Steinbach, <a href="/A000088/a000088_6.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 6

%H Peter Steinbach, <a href="/A000088/a000088_7.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 7

%H Peter Steinbach, <a href="/A000088/a000088_8.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 8

%H Peter Steinbach, <a href="/A000088/a000088_9.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 9

%H Peter Steinbach, <a href="/A000088/a000088_10.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 10

%H Peter Steinbach, <a href="/A000088/a000088_11.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 11

%H Peter Steinbach, <a href="/A000088/a000088_12.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 12

%H Peter Steinbach, <a href="/A000088/a000088_13.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 13

%H Peter Steinbach, <a href="/A000088/a000088_14.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 14

%H Peter Steinbach, <a href="/A000088/a000088_15.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 15

%H Peter Steinbach, <a href="/A000088/a000088_16.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 16

%H Peter Steinbach, <a href="/A000088/a000088_17.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 17

%H J. M. Tangen and N. J. A. Sloane, <a href="/A000666/a000666.pdf">Correspondence, 1976-1976</a>

%H James Turner, William H. Kautz, <a href="http://dx.doi.org/10.1137/1012125">A survey of progress in graph theory in the Soviet Union</a> SIAM Rev. 12 1970 suppl. iv+68 pp. MR0268074 (42 #2973). See p. 18.

%H S. Uijlen, B. Westerbaan, <a href="http://arxiv.org/abs/1412.8544">A Kochen-Specker system has at least 22 vectors</a>, arXiv preprint arXiv:1412.8544 [cs.DM], 2014.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SimpleGraph.html">Simple Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ConnectedGraph.html">Connected Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DegreeSequence.html">Degree Sequence</a>

%H E. M. Wright, <a href="http://dx.doi.org/10.1007/BF01350794">The number of graphs on many unlabelled nodes</a>, Mathematische Annalen, December 1969, Volume 183, Issue 4, 250-253

%H E. M. Wright, <a href="http://dx.doi.org/10.1090/S0002-9904-1972-13097-0 ">The number of unlabelled graphs with many nodes and edges</a> Bull. Amer. Math. Soc. Volume 78, Number 6 (1972), 1032-1034.

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%F 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

%F 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_, Oct 24 2005

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

%F 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).

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

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

%F ..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);

%F ..ord(c) = lcm{i : c_i>0};

%F ..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. (End)

%F 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

%F For asymptotics see also Lupanov 1959, 1960, also Turner and Kautz, p. 18. - _N. J. A. Sloane_, Apr 08 2014

%F 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

%F From _Keith Briggs_, Jun 24 2016: (Start)

%F a(n) = 2^binomial(n,2)/n!*(

%F 1+

%F 2^(- n+ 1)*n$2+

%F 2^(-2*n+ 3)*n$3*(n-7/3)+

%F 2^(-3*n+ 6)*n$4*(4*n^2/3-34*n/3+25)+

%F 2^(-4*n+10)*n$5*(8*n^3/3-142*n^2/3+2528*n/9-24914/45)+

%F 2^(-5*n+15)*n$6*(128*n^4/15-2296*n^3/9+25604*n^2/9-630554*n/45+25704)+

%F 2^(-6*n+21)*n$7*(2048*n^5/45-18416*n^4/9+329288*n^3/9-131680816*n^2/405+193822388*n/135-7143499196/2835)+

%F ...

%F )

%F where n$k is the falling factorial: n$k = n(n-1)(n-2)...(n-k+1), using the method of Wright 1969.

%F (End)

%p # To produce all graphs on 4 nodes, for example:

%p with(GraphTheory):

%p L:=[NonIsomorphicGraphs](4,output=graphs,outputform=adjacency): # _N. J. A. Sloane_, Oct 07 2013

%p seq(GraphTheory[NonIsomorphicGraphs](n,output=count),n=1..10); # _Juergen Will_, Jan 02 2018

%t Needs["Combinatorica`"]

%t Table[NumberOfGraphs[n], {n, 0, 19}] (* _Geoffrey Critzer_, Mar 12 2011 *)

%t permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];

%t edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];

%t a[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];

%t Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Jul 05 2018, after _Andrew Howroyd_ *)

%o (Sage)

%o def a(n):

%o return len(list(graphs(n)))

%o # _Ralf Stephan_, May 30 2014

%o (PARI)

%o permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}

%o edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, v[i]\2)}

%o a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ _Andrew Howroyd_, Oct 22 2017

%Y Partial sums of A002494.

%Y Cf. A001349 (connected graphs), A002218, A006290.

%Y Second column of A063841.

%Y Row sums of A008406.

%Y Cf. also A000055, A000664.

%K core,nonn,nice

%O 0,3

%A _N. J. A. Sloane_

%E 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 | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 14 12:36 EST 2018. Contains 317185 sequences. (Running on oeis4.)