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

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.

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 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. 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. 405-469.

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

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

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

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. Adams-Watters, Oct 23 2009

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 July 29 13:39 EDT 2016. Contains 275165 sequences.