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

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

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. - 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, 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. - 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 n-multigraphs 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^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

a(n) = a(n, 2) where a(n, t), the number of t-uniform 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 s|r with gcd(k, r/s) = 1) s*c_(k*s) (= the number of k-cycles 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

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.

Content is available under The OEIS End-User License Agreement .

Last modified October 20 07:01 EDT 2014. Contains 248329 sequences.