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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001349 Number of connected graphs with n nodes.
(Formerly M1657 N0649)
88
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)
OFFSET

0,4

COMMENTS

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]

REFERENCES

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

LINKS

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:1208.3892 [math.CO], 2012.

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

Jonathan Baker, Kevin N. Vander Meulen, Adam Van Tuyl, Shedding vertices of vertex decomposable well-covered graphs, Discrete Mathematics (2018) Vol. 341, Issue 12, 3355-3369. Also arXiv:1606.04447 [math.NT], 2016.

Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur and Hadrien Melot, House of Graphs: a database of interesting graphs, 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.

Matt DeVos, Adam Dyck, Jonathan Jedwab, Samuel Simon, Which graphs occur as gamma-graphs?, arXiv:1810.01583 [math.CO], 2018.

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)

Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.

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.

Richard J. Mathar, Counting Connected Graphs without Overlapping Cycles, arXiv:1808.06264 [math.CO], 2018.

B. D. McKay, Simple Graphs

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

Marius Möller, Laura Hindersin, Arne Traulsen, Exploring and mapping the universe of evolutionary graphs, arXiv:1810.12807 [q-bio.PE], 2018.

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

Yoav Spector, Moshe Schwartz, Study of potential Hamiltonians for quantum graphity, arXiv:1808.05632 [cond-mat.stat-mech], 2018.

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: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

FORMULA

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

EXAMPLE

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

MAPLE

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

with(GraphTheory):

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

MATHEMATICA

<<"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 *)

terms = 20;

mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];

EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];

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];

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

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

Join[{1}, EULERi[Array[a88, terms]]] (* Jean-François Alcover, Jul 28 2018, after Andrew Howroyd *)

PROG

(Sage)

property=lambda G: G.is_connected()

def a(n):

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

# Ralf Stephan, May 30 2014

CROSSREFS

Cf. A000088, A002218, A006290, A000719, A201922 (Multiset transform).

Row sums of A054924.

Sequence in context: A128527 A076328 A128528 * A126060 A266934 A182157

Adjacent sequences:  A001346 A001347 A001348 * A001350 A001351 A001352

KEYWORD

nonn,core,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

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

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 20 17:13 EDT 2019. Contains 321345 sequences. (Running on oeis4.)