|
%I M1657 N0649 #174 Feb 16 2023 09:04:12
%S 1,1,1,2,6,21,112,853,11117,261080,11716571,1006700565,164059830476,
%T 50335907869219,29003487462848061,31397381142761241960,
%U 63969560113225176176277,245871831682084026519528568,1787331725248899088890200576580,24636021429399867655322650759681644
%N Number of connected graphs with n nodes.
%C The singleton graph K_1 is considered connected even though it is conventionally taken to have vertex connectivity 0. - _Eric W. Weisstein_, Jul 21 2020
%C 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]
%D 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.
%D 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.
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, page 48, c(x). Also page 242.
%D 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).
%D 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.
%D R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
%D R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1978.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D Robin J. Wilson, Introduction to Graph Theory, Academic Press, 1972. (But see A126060!)
%H N. J. A. Sloane, <a href="/A001349/b001349.txt">Table of n, a(n) for n = 0..75</a> [Computed using Keith Briggs's values for A000088]
%H Michal Adamaszek, <a href="http://arxiv.org/abs/1208.3892">Small flag complexes with torsion</a>, arXiv:1208.3892 [math.CO], 2012.
%H C. O. Aguilar, B. Gharesifard, <a href="https://mast.queensu.ca/~bahman/CA-BG-2014.pdf">Graph Controllability Classes for the Laplacian Leader-Follower Dynamics</a>, 2014. See Table 1.
%H Jonathan Baker, Kevin N. Vander Meulen, Adam Van Tuyl, <a href="https://doi.org/10.1016/j.disc.2018.07.029">Shedding vertices of vertex decomposable well-covered graphs</a>, Discrete Mathematics (2018) Vol. 341, Issue 12, 3355-3369. Also <a href="https://arxiv.org/abs/1606.04447">arXiv:1606.04447</a> [math.NT], 2016.
%H Johannes Bausch, Felix Leditzky, <a href="https://arxiv.org/abs/1910.00471">Error Thresholds for Arbitrary Pauli Noise</a>, arXiv:1910.00471 [quant-ph], 2019.
%H Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur and Hadrien Melot, <a href="http://arxiv.org/abs/1204.3549">House of Graphs: a database of interesting graphs</a>, arXiv:1204.3549 [math.CO], 2012.
%H P. Butler and R. W. Robinson, <a href="/A002218/a002218.pdf">On the computer calculation of the number of nonseparable graphs</a>, 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]
%H P. J. Cameron, <a href="http://dx.doi.org/10.1016/0012-365X(89)90081-2">Some sequences of integers</a>, Discrete Math., 75 (1989), 89-102.
%H P. J. Cameron, <a href="http://dx.doi.org/10.1016/S0167-5060(08)70569-7">Some sequences of integers</a>, in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
%H P. J. Cameron, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H CombOS - Combinatorial Object Server, <a href="http://combos.org/nauty">Generate graphs</a>
%H Matt DeVos, Adam Dyck, Jonathan Jedwab, Samuel Simon, <a href="https://arxiv.org/abs/1810.01583">Which graphs occur as gamma-graphs?</a>, arXiv:1810.01583 [math.CO], 2018.
%H J. P. Dolch, <a href="/A001349/a001349.pdf">Names of Hamiltonian graphs</a>, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 259-271. (Annotated scanned copy of 3 pages)
%H Steven R. Finch, <a href="https://doi.org/10.1017/9781316997741">Mathematical Constants II</a>, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
%H E. Friedman, <a href="/A000088/a000088a.gif">Illustration of small graphs</a>
%H F. Harary, <a href="http://dx.doi.org/10.1090/S0002-9947-1955-0068198-2">The number of linear, directed, rooted, and connected graphs</a>, Trans. Am. Math. Soc. 78 (1955) 445-463.
%H Avraham Itzhakov, Michael Codish, <a href="https://modref.github.io/papers/ModRef2019_Incremental%20Symmetry%20Breaking%20Constraints%20for%20Graph%20Search%20Problems.pdf">Incremental Symmetry Breaking Constraints for Graph Search Problems</a>, Ben-Gurion University of the Negev (Beer-Sheva, Israel, 2019).
%H X. Li, D. S. Stones, H. Wang, H. Deng, X. Liu and G, Wang, <a href="http://dx.doi.org/10.1371/journal.pone.0050093">NetMODE: Network Motif Detection without Nauty</a>, PLoS ONE 7(12): e50093. - From _N. J. A. Sloane_, Feb 02 2013
%H Steffen Lauritzen, Alessandro Rinaldo, Kayvan Sadeghi, <a href="https://arxiv.org/abs/1709.03885">On Exchangeability in Network Models</a>, arXiv:1709.03885 [math.ST], 2017.
%H Richard J. Mathar, <a href="https://arxiv.org/abs/1808.06264">Counting Connected Graphs without Overlapping Cycles</a>, arXiv:1808.06264 [math.CO], 2018.
%H B. D. McKay, <a href="http://users.cecs.anu.edu.au/~bdm/data/graphs.html">Simple Graphs</a>
%H A. Milicevic and N. Trinajstic, <a href="http://www.sicmm.org/~FAMNIT-knjiga/wwwANG/web-pages/405_469_tcm18-67839%5B1%5D.pdf">Combinatorial Enumeration in Chemistry</a>, Chem. Modell., Vol. 4, (2006), pp. 405-469.
%H Marius Möller, Laura Hindersin, Arne Traulsen, <a href="https://arxiv.org/abs/1810.12807">Exploring and mapping the universe of evolutionary graphs</a>, arXiv:1810.12807 [q-bio.PE], 2018.
%H Marius Möller, Laura Hindersin, Arne Traulsen, <a href="https://www.nature.com/articles/s42003-019-0374-x">Exploring and mapping the universe of evolutionary graphs identifies structural properties affecting fixation probability and time</a>, Communications Biology 2 (2019), Article number: 137.
%H L. Naughton, G. Pfeiffer, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Naughton/naughton2.html">Integer Sequences Realized by the Subgroup Pattern of the Symmetric Group</a>, J. Int. Seq. 16 (2013) #13.5.8
%H M. Petkovsek and T. Pisanski, <a href="http://hrcak.srce.hr/file/4232">Counting disconnected structures: chemical trees, fullerenes, I-graphs and others</a>, Croatica Chem. Acta, 78 (2005), 563-567.
%H R. W. Robinson, <a href="http://dx.doi.org/10.1016/S0021-9800(70)80089-8">Enumeration of non-separable graphs</a>, J. Combin. Theory 9 (1970), 327-356.
%H Gordon Royle, <a href="http://staffhome.ecm.uwa.edu.au/~00013890/remote/graphs/">Small graphs</a>
%H Yoav Spector, Moshe Schwartz, <a href="https://arxiv.org/abs/1808.05632">Study of potential Hamiltonians for quantum graphity</a>, arXiv:1808.05632 [cond-mat.stat-mech], 2018.
%H M. L. Stein and P. R. Stein, <a href="http://dx.doi.org/10.2172/4180737">Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points</a>. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967.
%H Peter Steinbach, <a href="/A000088/a000088_17.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
%H D. Stolee, <a href="http://arxiv.org/abs/1104.5261">Isomorph-free generation of 2-connected graphs with applications</a>, arXiv:1104.5261 [math.CO], 2011.
%H Rodrigo Stange Tessinari, Marcia Helena Moreira Paiva, Maxwell E. Monteiro, Marcelo E. V. Segatto, Anilton Garcia, George T. Kanellos, Reza Nejabati, Dimitra Simeonidou, <a href="https://doi.org/10.1109/BICOP.2018.8658361">On the Impact of the Physical Topology on the Optical Network Performance</a>, IEEE British and Irish Conference on Optics and Photonics (BICOP 2018), London.
%H James Turner, William H. Kautz, <a href="http://dx.doi.org/10.1137/1012125">A survey of progress in graph theory in the Soviet Union</a> SIAM Rev. 12 1970 suppl. iv+68 pp. MR0268074 (42 #2973). See p. 18. - _N. J. A. Sloane_, Apr 08 2014
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ConnectedGraph.html">Connected Graph.</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/k-ConnectedGraph.html">k-Connected Graph</a>
%H Myung-Gon Yoon, Peter Rowlinson, Dragos Cvetkovic, Zoran Stanic, <a href="https://doi.org/10.1002/asjc.793">Controllability of multi-agent dynamical systems with a broadcasting control signal</a>, Asian J. Control 16 (4) (2014) 1066-1072, Table 1.
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F For asymptotics see Lupanov 1959, 1960, also Turner and Kautz, p. 18. - _N. J. A. Sloane_, Apr 08 2014
%e G.f. = 1 + x + x^2 + 2*x^3 + 6*x^4 + 21*x^5 + 112*x^6 + 853*x^7 + ....
%p # To produce all connected graphs on 4 nodes, for example (from _N. J. A. Sloane_, Oct 07 2013):
%p with(GraphTheory):
%p L:=[NonIsomorphicGraphs](4,output=graphs,outputform=adjacency, restrictto=connected):
%t <<"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 *)
%t terms = 20;
%t mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
%t 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]];
%t 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];
%t edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
%t a88[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
%t Join[{1}, EULERi[Array[a88, terms]]] (* _Jean-François Alcover_, Jul 28 2018, after _Andrew Howroyd_ *)
%o (Sage)
%o property=lambda G: G.is_connected()
%o def a(n):
%o return len([1 for G in graphs(n) if property(G)])
%o # _Ralf Stephan_, May 30 2014
%Y Cf. A000088, A002218, A006290, A000719, A201922 (Multiset transform).
%Y Row sums of A054924.
%K nonn,core,nice
%O 0,4
%A _N. J. A. Sloane_
%E More terms from Ronald C. Read
|
