A327114 Number of labeled simple graphs covering n vertices with cut-connectivity 1.

0, 0, 0, 3, 28, 490, 15336, 851368, 85010976, 15615858960, 5388679220480, 3548130389657216, 4507988483733389568, 11145255551131555572992, 53964198507018134569758720, 514158235191699333805861463040

Offset

0,4

Comments

The cut-connectivity of a graph is the minimum number of vertices that must be removed (along with any empty or duplicate edges) to obtain a disconnected or empty graph.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..50

Formula

a(n) = A001187(n) - A013922(n), if we assume A001187(1) = 0.

Mathematica

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]], {2}], Length[Intersection@@s[[#]]]>0&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
cutConnSys[vts_, eds_]:=If[Length[vts]==1, 1, Min@@Length/@Select[Subsets[vts], Function[del, csm[DeleteCases[DeleteCases[eds, Alternatives@@del, {2}], {}]]!={Complement[vts, del]}]]];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Union@@#==Range[n]&&cutConnSys[Range[n], #]==1&]], {n, 0, 3}]

Prog

(PARI) seq(n)={my(g=log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n))); Vec(serlaplace(g-intformal(1+log(x/serreverse(x*deriv(g))))), -(n+1))} \\ Andrew Howroyd, Sep 11 2019

Crossrefs

Column k = 1 of A327126.

The unlabeled version is A052442, if we assume A052442(2) = 0.

Connected non-separable graphs are A013922.

BII-numbers for cut-connectivity 1 are A327098.

Set-systems with cut-connectivity 1 are counted by A327197.

Labeled simple graphs with vertex-connectivity 1 are A327336.

Cf. A001187, A054592, A259862, A322389, A322390, A326786, A327070, A327100, A327125.

Sequence in context: A327071 A346315 A058804 * A327336 A355473 A180710

Adjacent sequences: A327111 A327112 A327113 * A327115 A327116 A327117

Keyword

nonn

Author

Gus Wiseman, Aug 25 2019

Status

approved