login
Number of unlabeled nonseparable (or 2-connected) graphs (or blocks) with n nodes.
(Formerly M2873 N1155)
56

%I M2873 N1155 #130 Feb 26 2023 20:13:19

%S 0,1,1,3,10,56,468,7123,194066,9743542,900969091,153620333545,

%T 48432939150704,28361824488394169,30995890806033380784,

%U 63501635429109597504951,244852079292073376010411280,1783160594069429925952824734641,24603887051350945867492816663958981

%N Number of unlabeled nonseparable (or 2-connected) graphs (or blocks) with n nodes.

%C By definition, a(n) gives the number of graphs with zero cutpoints. - _Travis Hoppe_, Apr 28 2014

%C For n > 2, a(n) is also the number of simple biconnected graphs on n nodes. - _Eric W. Weisstein_, Dec 07 2021

%C This sequence follows R. W. Robinson's definition of a nonseparable graph which includes K_2 but not the singleton graph K_1. This definition is most suited to graphical enumeration. Other authors sometimes include K_1 as a block or exclude K_2 as not 2-connected. - _Andrew Howroyd_, Feb 26 2023

%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 E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 188.

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

%H Andrew Howroyd, <a href="/A002218/b002218.txt">Table of n, a(n) for n = 1..40</a> [terms 1..26 from R. W. Robinson]

%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 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 R. W. Robinson, <a href="/A002218/a002218_1.pdf">Computer print-out of first 26 terms</a> [Annotated scanned copy]

%H R. W. Robinson, <a href="http://cobweb.cs.uga.edu/~rwr/publications/tables.pdf">Tables</a>

%H R. W. Robinson, <a href="/A002218/a002218_2.pdf">Tables</a> [Local copy, with permission]

%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 R. W. Robinson and T. R. S. Walsh, <a href="http://cobweb.cs.uga.edu/~rwr/publications/cycleindex.pdf">Inversion of cycle index sum relations for 2- and 3-connected graphs</a>, J. Combin. Theory Ser. B. 57 (1993), 289-308.

%H R. W. Robinson and T. R. S. Walsh, <a href="https://doi.org/10.1006/jctb.1993.1022">Inversion of cycle index sum relations for 2- and 3-connected graphs</a>, J. Combin. Theory Ser. B. 57 (1993), 289-308.

%H Andrés Santos, <a href="https://doi.org/10.1007/978-3-319-29668-5_3">Density Expansion of the Equation of State</a>, in A Concise Course on the Theory of Classical Liquids, Volume 923 of the series Lecture Notes in Physics, pp 33-96, 2016. DOI:10.1007/978-3-319-29668-5_3. See Reference 40.

%H Andrew J. Schultz and David A. Kofke, <a href="https://doi.org/10.1103/PhysRevE.90.023301">Fifth to eleventh virial coefficients of hard spheres</a>, Phys. Rev. E 90, 023301, 4 August 2014

%H D. Stolee, <a href="http://arxiv.org/abs/1104.5261">Isomorph-free generation of 2-connected graphs with applications</a>, arXiv preprint 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, and 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BiconnectedGraph.html">Biconnected Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/k-ConnectedGraph.html">k-Connected Graph</a>

%o (PARI) \\ See A004115 for graphsSeries and A339645 for combinatorial species functions.

%o cycleIndexSeries(n)={my(g=graphsSeries(n), gc=sLog(g), gcr=sPoint(gc)); intformal(x*sSolve( sLog( gcr/(x*sv(1)) ), gcr ), sv(1)) + sSolve(subst(gc, sv(1), 0), gcr)}

%o { my(N=12); Vec(OgfSeries(cycleIndexSeries(N)), -N) } \\ _Andrew Howroyd_, Dec 28 2020

%Y Column k=0 of A325111 (for n>1).

%Y Column sums of A339070.

%Y Row sums of A339071.

%Y The labeled version is A013922.

%Y Cf. A000088 (graphs), A001349 (connected graphs), A006289, A006290, A004115 (rooted case), A010355 (by edges), A241767.

%K nonn,nice

%O 1,4

%A _N. J. A. Sloane_

%E More terms from Ronald C. Read. Robinson and Walsh list the first 26 terms.

%E a(1) changed from 0 to 1 by _Eric W. Weisstein_, Dec 07 2021

%E a(1) restored to 0 by _Andrew Howroyd_, Feb 26 2023