login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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.

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 Cybernetics [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.

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

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

LINKS

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 [cs.DM], 2013.

Natalie Arkus, Vinothan N. Manoharan, Michael P. Brenner. Deriving Finite Sphere Packings, arXiv:1011.5412 [cond-mat.soft], 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 [quant-ph], 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 [math.CO], 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, Some sequences of integers, Discrete Math., 75 (1989), 89-102.

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

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

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 number of structures of finite relations, Proc. Amer. Math. Soc. 4 (1953), 486-495.

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 [cs.SI], 2012.

S. Hougardy, Home Page

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

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 [math.GT], 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.

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.

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.

R. W. Robinson, Enumeration of non-separable graphs, J. Combin. Theory 9 (1970), 327-356.

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

James Turner, William H. Kautz, 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.

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

E. M. Wright, The number of graphs on many unlabelled nodes, Mathematische Annalen, December 1969, Volume 183, Issue 4, 250-253

E. M. Wright, The number of unlabelled graphs with many nodes and edges Bull. Amer. Math. Soc. Volume 78, Number 6 (1972), 1032-1034.

Index entries for "core" sequences

FORMULA

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, 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/(Product_{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. (End)

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

From Keith Briggs, Jun 24 2016: (Start)

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

   1+

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

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

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

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

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

   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)+

   ...

)

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

(End)

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

Needs["Combinatorica`"]

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,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

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

STATUS

approved

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 June 29 22:51 EDT 2016. Contains 274302 sequences.