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

Author

Gus Wiseman, Aug 25 2019

Keywords

• nonn

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

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.

Programs

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}]

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

Formula

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