This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001349 Number of connected graphs with n nodes.
(Formerly M1657 N0649)
1, 1, 1, 2, 6, 21, 112, 853, 11117, 261080, 11716571, 1006700565, 164059830476, 50335907869219, 29003487462848061, 31397381142761241960, 63969560113225176176277, 245871831682084026519528568, 1787331725248899088890200576580, 24636021429399867655322650759681644 (list; graph; refs; listen; history; text; internal format)



Inverse Euler transform of A000088 but with a(0) omitted so that Sum_{k>=0} A000088(n) * x^n = Product_{k>0} (1 - x^k)^-a(k). It is debatable if there is a connected graph with 0 nodes and so a(0)=0 or better start from a(1)=1. - Michael Somos, Jun 01 2013. [As Harary once remarked in a famous paper ("Is the null-graph a pointless concept?"), the empty graph has every property, which is why a(0)=1. - N. J. A. Sloane, Apr 08 2014]


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.

F. Harary and R. C. Read, Is the null-graph a pointless concept?, pp. 37-44 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, page 48, c(x). Also page 242.

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.

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

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

Robin J. Wilson, Introduction to Graph Theory, Academic Press, 1972. (But see A126060!)


N. J. A. Sloane, Table of n, a(n) for n = 0..75 [Computed using Keith Briggs's values for A000088]

Michal Adamaszek, Small flag complexes with torsion, arXiv preprint arXiv:1208.3892 [math.CO], 2012.

C. O. Aguilar, B. Gharesifard, Graph Controllability Classes for the Laplacian Leader-Follower Dynamics, 2014. See Table 1.

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.

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)

E. Friedman, Illustration of small graphs

F. Harary, The number of linear, directed, rooted, and connected graphs, Trans. Am. Math. Soc. 78 (1955) 445-463.

X. Li, D. S. Stones, H. Wang, H. Deng, X. Liu and G, Wang, NetMODE: Network Motif Detection without Nauty, PLoS ONE 7(12): e50093. - From N. J. A. Sloane, Feb 02 2013

Steffen Lauritzen, Alessandro Rinaldo, Kayvan Sadeghi, On Exchangeability in Network Models, arXiv:1709.03885 [math.ST] 2017.

B. D. McKay, Simple Graphs

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

L. Naughton, G. Pfeiffer, Integer Sequences Realized by the Subgroup Pattern of the Symmetric Group, J. Int. Seq. 16 (2013) #13.5.8

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

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

Gordon Royle, Small graphs

M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967.

Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

D. Stolee, Isomorph-free generation of 2-connected graphs with applications, arXiv preprint arXiv:1104.5261 [math.CO], 2011.

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. - N. J. A. Sloane, Apr 08 2014

Eric Weisstein's World of Mathematics, Connected Graph.

Eric Weisstein's World of Mathematics, k-Connected Graph

Index entries for "core" sequences


For asymptotics see Lupanov 1959, 1960, also Turner and Kautz, p. 18. - N. J. A. Sloane, Apr 08 2014


G.f. = 1 + x + x^2 + 2*x^3 + 6*x^4 + 21*x^5 + 112*x^6 + 853*x^7 + ....


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


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


<<"Combinatorica`"; max = 19; A000088 = Table[ NumberOfGraphs[n], {n, 0, max}]; f[x_] = 1 - Product[ 1/(1 - x^k)^a[k], {k, 1, max}]; a[0] = a[1] = a[2] = 1; coes = CoefficientList[ Series[ f[x], {x, 0, max}], x]; sol = First[ Solve[ Thread[ Rest[ coes + A000088 ] == 0]]]; Table[ a[n], {n, 0, max}] /. sol (* Jean-Fran├žois Alcover, Nov 24 2011 *)



property=lambda G: G.is_connected()

def a(n):

    return len(filter(property, graphs(n)))

# Ralf Stephan, May 30 2014


Cf. A000088, A002218, A006290, A000719, A201922 (Multiset transform). Row sums of A054924.

Sequence in context: A076328 A128527 A128528 * A126060 A266934 A182157

Adjacent sequences:  A001346 A001347 A001348 * A001350 A001351 A001352




N. J. A. Sloane


More terms from R. C. Read (rcread(AT)math.uwaterloo.ca).

Link fixed by Franklin T. Adams-Watters, Oct 23 2009



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 July 23 13:25 EDT 2018. Contains 312932 sequences. (Running on oeis4.)