login
A327114
Number of labeled simple graphs covering n vertices with cut-connectivity 1.
15
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
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.
Sequence in context: A327071 A346315 A058804 * A327336 A355473 A180710
KEYWORD
nonn
AUTHOR
Gus Wiseman, Aug 25 2019
STATUS
approved