

A001349


Number of connected graphs with n nodes.
(Formerly M1657 N0649)


62



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 nullgraph 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 nullgraph a pointless concept?, pp. 3744 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. SpringerVerlag, 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 498500. 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): 521.
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).
M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967.
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 preprint arXiv:1208.3892 [math.CO], 2012.
C. O. Aguilar, B. Gharesifard, Graph Controllability Classes for the Laplacian LeaderFollower 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), 89102.
P. J. Cameron, Some sequences of integers, in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89102.
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 SE Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 259271. (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) 445463.
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. doi:10.1371/journal.pone.0050093.  From N. J. A. Sloane, Feb 02 2013
A. Milicevic and N. Trinajstic, Combinatorial Enumeration in Chemistry, Chem. Modell., Vol. 4, (2006), pp. 405469.
M. Petkovsek and T. Pisanski, Counting disconnected structures: chemical trees, fullerenes, Igraphs and others, Croatica Chem. Acta, 78 (2005), 563567.
R. W. Robinson, Enumeration of nonseparable graphs, J. Combin. Theory 9 (1970), 327356.
Gordon Royle, Small graphs
D. Stolee, Isomorphfree generation of 2connected 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, kConnected 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 (* JeanFrançois Alcover, Nov 24 2011 *)


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. Row sums of A054924.
Sequence in context: A076328 A128527 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).
Link fixed by Franklin T. AdamsWatters, Oct 23 2009


STATUS

approved



