A004115 -id:A004115 - cp's OEIS frontend

A013922 Number of labeled connected graphs with n nodes and 0 cutpoints (blocks or nonseparable graphs).

0, 1, 1, 10, 238, 11368, 1014888, 166537616, 50680432112, 29107809374336, 32093527159296128, 68846607723033232640, 290126947098532533378816, 2417684612523425600721132544, 40013522702538780900803893881856

Offset: 1

Stanley Selkow (sms(AT)owl.WPI.EDU)

Or, number of labeled 2-connected graphs with n nodes.

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p.402.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 9.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.20(b), g(n).

Andrew Howroyd, Table of n, a(n) for n = 1..50 (terms 1..25 from R. W. Robinson)
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002 [Local copy, with permission]
Thomas Lange, Biconnected reliability, Hochschule Mittweida (FH), Fakultät Mathematik/Naturwissenschaften/Informatik, Master's Thesis, 2015.
Andrés Santos, Density Expansion of the Equation of State, 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.
S. Selkow, The enumeration of labeled graphs by number of cutpoints, Discr. Math. 185 (1998), 183-191.

Cf. A002218, A004115, A095983.

Row sums of triangle A123534.

seq[n_] := CoefficientList[Log[x/InverseSeries[x*D[Log[Sum[2^Binomial[k, 2]*x^k/k!, {k, 0, n}] + O[x]^n], x]]], x]*Range[0, n-2]!;
seq[16] (* Jean-François Alcover, Aug 19 2019, after Andrew Howroyd *)

seq(n)={Vec(serlaplace(log(x/serreverse(x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n)))))), -n)} \\ Andrew Howroyd, Sep 26 2018

Harary and Palmer give e.g.f. in Eqn. (1.3.3) on page 10.

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

Original entry on oeis.org

0, 1, 1, 3, 10, 56, 468, 7123, 194066, 9743542, 900969091, 153620333545, 48432939150704, 28361824488394169, 30995890806033380784, 63501635429109597504951, 244852079292073376010411280, 1783160594069429925952824734641, 24603887051350945867492816663958981

Offset: 1

N. J. A. Sloane

By definition, a(n) gives the number of graphs with zero cutpoints. - Travis Hoppe, Apr 28 2014
For n > 2, a(n) is also the number of simple biconnected graphs on n nodes. - Eric W. Weisstein, Dec 07 2021
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

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

Andrew Howroyd, Table of n, a(n) for n = 1..40 [terms 1..26 from R. W. Robinson]
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]
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
R. W. Robinson, Computer print-out of first 26 terms [Annotated scanned copy]
R. W. Robinson, Tables
R. W. Robinson, Tables [Local copy, with permission]
R. W. Robinson, Enumeration of non-separable graphs, J. Combin. Theory 9 (1970), 327-356.
R. W. Robinson and T. R. S. Walsh, Inversion of cycle index sum relations for 2- and 3-connected graphs, J. Combin. Theory Ser. B. 57 (1993), 289-308.
R. W. Robinson and T. R. S. Walsh, Inversion of cycle index sum relations for 2- and 3-connected graphs, J. Combin. Theory Ser. B. 57 (1993), 289-308.
Andrés Santos, Density Expansion of the Equation of State, 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.
Andrew J. Schultz and David A. Kofke, Fifth to eleventh virial coefficients of hard spheres, Phys. Rev. E 90, 023301, 4 August 2014
D. Stolee, Isomorph-free generation of 2-connected graphs with applications, arXiv preprint arXiv:1104.5261 [math.CO], 2011.
Rodrigo Stange Tessinari, Marcia Helena Moreira Paiva, Maxwell E. Monteiro, Marcelo E. V. Segatto, Anilton Garcia, George T. Kanellos, Reza Nejabati, and Dimitra Simeonidou, On the Impact of the Physical Topology on the Optical Network Performance, IEEE British and Irish Conference on Optics and Photonics (BICOP 2018), London.
Eric Weisstein's World of Mathematics, Biconnected Graph
Eric Weisstein's World of Mathematics, k-Connected Graph

Column k=0 of A325111 (for n>1).
Column sums of A339070.
Row sums of A339071.
The labeled version is A013922.
Cf. A000088 (graphs), A001349 (connected graphs), A006289, A006290, A004115 (rooted case), A010355 (by edges), A241767.

\\ See A004115 for graphsSeries and A339645 for combinatorial species functions.
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)}
{ my(N=12); Vec(OgfSeries(cycleIndexSeries(N)), -N) } \\ Andrew Howroyd, Dec 28 2020

More terms from Ronald C. Read. Robinson and Walsh list the first 26 terms.
a(1) changed from 0 to 1 by Eric W. Weisstein, Dec 07 2021
a(1) restored to 0 by Andrew Howroyd, Feb 26 2023

A007146 Number of unlabeled simple connected bridgeless graphs with n nodes.

Original entry on oeis.org

1, 0, 1, 3, 11, 60, 502, 7403, 197442, 9804368, 902818087, 153721215608, 48443044675155, 28363687700395422, 30996524108446916915, 63502033750022111383196, 244852545022627009655180986, 1783161611023802810566806448531, 24603891215865809635944516464394339

Offset: 1

N. J. A. Sloane

Also unlabeled simple graphs with spanning edge-connectivity >= 2. The spanning edge-connectivity of a set-system is the minimum number of edges that must be removed (without removing incident vertices) to obtain a set-system that is disconnected or covers fewer vertices. - Gus Wiseman, Sep 02 2019

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..40 (terms 1..22 from R. J. Mathar)
P. Hanlon and R. W. Robinson, Counting bridgeless graphs, J. Combin. Theory, B 33 (1982), 276-305, Table III.
Eric Weisstein's World of Mathematics, Bridgeless Graph
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Simple Graph
Gus Wiseman, The a(3) = 1 through a(5) = 11 connected bridgeless graphs.

Cf. A005470 (number of simple graphs).
Cf. A007145 (number of simple connected rooted bridgeless graphs).
Cf. A052446 (number of simple connected bridged graphs).
Cf. A263914 (number of simple bridgeless graphs).
Cf. A263915 (number of simple bridged graphs).
The labeled version is A095983.
Row sums of A263296 if the first two columns are removed.
BII-numbers of set-systems with spanning edge-connectivity >= 2 are A327109.
Graphs with non-spanning edge-connectivity >= 2 are A327200.
2-vertex-connected graphs are A013922.
Cf. A000719, A001349, A002494, A261919, A327069, A327071, A327074, A327075, A327077, A327109, A327144, A327146.

\\ Translation of theorem 3.2 in Hanlon and Robinson reference. See A004115 for graphsSeries and A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(gc=sLog(graphsSeries(n)), gcr=sPoint(gc)); sSolve( gc + gcr^2/2 - sRaise(gcr,2)/2, x*sv(1)*sExp(gcr) )}
NumUnlabeledObjsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 31 2020

a(n) = A001349(n) - A052446(n). - Gus Wiseman, Sep 02 2019

Reference gives first 22 terms.

A241767 Number of simple connected graphs with n nodes and exactly 1 articulation point (cutpoints).

Original entry on oeis.org

0, 0, 1, 2, 7, 33, 244, 2792, 52448, 1690206, 96288815, 9873721048, 1841360945834, 629414405238720, 397024508142598996, 464923623652122023478, 1016016289424631486429082, 4162473006943138723685574978, 32096861904411547975392065322659

Offset: 1

Travis Hoppe and Anna Petrone, Apr 28 2014

nonn

Terms may be computed from A004115. See formula. There is an obvious bijection between a connected graph with 1 articulation point and a multiset of at least two rooted nonseparable graphs joined at the root node. - Andrew Howroyd, Nov 24 2020

Andrew Howroyd, Table of n, a(n) for n = 1..26
Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
T. Hoppe and A. Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
Eric Weisstein's World of Mathematics, Articulation Vertex

Column k=1 of A325111.
Cf. other simple connected graph sequences with k articulation points A002218, A241767, A241768, A241769, A241770, A241771.
Cf. A004115 (rooted and without articulation points).

G.f.: x/(Product_{k>=1} (1 - x^k)^A004115(k+1)) - x - Sum_{k>=1} A004115(k)*x^k. - Andrew Howroyd, Nov 24 2020

Terms a(11) and beyond from Andrew Howroyd, Nov 24 2020

A322396 Number of unlabeled simple connected graphs with n vertices whose bridges are all leaves, meaning at least one end of any bridge is an endpoint of the graph.

Original entry on oeis.org

1, 1, 1, 2, 5, 18, 98, 779, 10589, 255790, 11633297, 1004417286, 163944008107, 50324877640599, 29001521193534445, 31396727025729968365, 63969154112074956299242, 245871360738448777028919520, 1787330701747389106609369225312, 24636017249593067184544456944967278

Offset: 0

Gus Wiseman, Dec 06 2018

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..25
Eric Weisstein's World of Mathematics, Graph Bridge
Eric Weisstein's World of Mathematics, Endpoint
Gus Wiseman, The a(5) = 18 simple connected graphs whose bridges are all leaves.

Cf. A001187, A006125, A007146, A013922, A054921, A095983, A322338, A322394, A322395.

\\ See A004115 for graphsSeries and A339645 for combinatorial species functions.
bridgelessGraphs(n)={my(gc=sLog(graphsSeries(n)), gcr=sPoint(gc)); sSolve( gc + gcr^2/2 - sRaise(gcr,2)/2, x*sv(1)*sExp(gcr) )}
cycleIndexSeries(n)={1+sSubstOp(bridgelessGraphs(n), symGroupSeries(n))}
NumUnlabeledObjsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 31 2020

a(6)-a(10) from Andrew Howroyd, Dec 08 2018

Terms a(11) and beyond from Andrew Howroyd, Dec 31 2020

A007145 Number of rooted bridgeless graphs with n nodes.

Original entry on oeis.org

1, 0, 1, 4, 24, 193, 2420, 47912, 1600524, 93253226, 9694177479, 1822463625183, 625829508087155, 395785845695978077, 464137111800208818956, 1015091598240432264958267, 4160447480034069826186309689, 32088552194861245127627790541334

Offset: 1

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..40 (terms 1..22 from R. J. Mathar, terms 21..22 corrected by Andrew Howroyd)
P. Hanlon and R. W. Robinson, Counting bridgeless graphs, J. Combin. Theory, B 33 (1982), 276-305.

Cf. A004115, A007146.

\\ See A004115 for graphsSeries and A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(g=graphsSeries(n), gcr=sPoint(g)/g); sSolve( gcr, x*sv(1)*sExp(gcr) )}
NumUnlabeledObjsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 27 2020

Reference gives first 22 terms (terms a(21) and a(22) contain typos).

More terms from R. J. Mathar, Jun 06 2007

A340028 Number of unlabeled 2-connected graphs with n vertices rooted at a pair of noninterchangeable vertices.

Original entry on oeis.org

0, 1, 1, 7, 55, 655, 11147, 287791, 11787747, 804475261, 94875366649, 19825870580671, 7466490852631207, 5129453728126116131, 6487332587944013948099, 15213161506747424007012971, 66536415576917924594383104139, 545371527333985035460963541248785

Offset: 1

Andrew Howroyd, Jan 02 2021

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..30

Cf. A002218, A004115, A241768, A304070, A304074, A340029.

\\ See A004115 for graphsSeries and A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(g=graphsSeries(n), gcr=sPoint(g)/g); x*sPoint(sSolve( sLog( gcr/(x*sv(1)) ), gcr ))}
{ my(N=15); Vec(OgfSeries(cycleIndexSeries(N)), -N) }

A340029 Number of unlabeled 2-connected graphs with n vertices rooted at a pair of indistinguishable vertices.

Original entry on oeis.org

0, 1, 1, 6, 37, 388, 6004, 148759, 5974184, 404509191, 47552739892, 9923861406343, 3735194287263442, 2565376853616300801, 3244070698095148283628, 7607050619214875184974489, 33269229977451262849539412860, 272689940536978851416633440863567

Offset: 1

Andrew Howroyd, Jan 02 2021

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..30

Cf. A002218, A004115, A241768, A303829, A303831, A340028.

\\ See A004115 for graphsSeries and A339645 for combinatorial species functions.
blockGraphs(n)={my(gc=sLog(graphsSeries(n)), gcr=sPoint(gc)); intformal(x*sSolve( sLog( gcr/(x*sv(1)) ), gcr ), sv(1)) + sSolve(subst(gc, sv(1), 0), gcr)}
cycleIndexSeries(n)={sCartProd(blockGraphs(n), x^2 * symGroupCycleIndex(2) * symGroupSeries(n-2))}
{ my(N=15); Vec(OgfSeries(cycleIndexSeries(N)), -N) }

cp's OEIS Frontend

A013922 Number of labeled connected graphs with n nodes and 0 cutpoints (blocks or nonseparable graphs).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A007146 Number of unlabeled simple connected bridgeless graphs with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A241767 Number of simple connected graphs with n nodes and exactly 1 articulation point (cutpoints).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A322396 Number of unlabeled simple connected graphs with n vertices whose bridges are all leaves, meaning at least one end of any bridge is an endpoint of the graph.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A007145 Number of rooted bridgeless graphs with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Extensions

A340028 Number of unlabeled 2-connected graphs with n vertices rooted at a pair of noninterchangeable vertices.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A340029 Number of unlabeled 2-connected graphs with n vertices rooted at a pair of indistinguishable vertices.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI