A327198 - OEIS

A327198

Number of labeled simple graphs covering n vertices with vertex-connectivity 2.

0, 0, 0, 1, 9, 212, 9600, 789792, 114812264, 29547629568, 13644009626400, 11489505388892800, 17918588321874717312, 52482523149603539181312, 292311315623259148521270784, 3129388799344153886272170009600, 64965507855114369076680860799267840

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,5

COMMENTS

The vertex-connectivity of a set-system is the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain a non-connected set-system or singleton. Note that this means a single node has vertex-connectivity 0.

LINKS

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

Gus Wiseman, The a(4) = 9 simple covering graphs with vertex-connectivity 2.

FORMULA

a(n) = A013922(n) - A005644(n) for n >= 3. - Andrew Howroyd, Dec 26 2020

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

vertConnSys[vts_, eds_]:=Min@@Length/@Select[Subsets[vts], Function[del, Length[del]==Length[vts]-1||csm[DeleteCases[DeleteCases[eds, Alternatives@@del, {2}], {}]]!={Complement[vts, del]}]];

Table[Length[Select[Subsets[Subsets[Range[n], {2}]], vertConnSys[Range[n], #]==2&]], {n, 0, 5}]

CROSSREFS

The unlabeled version is A052443.

Cf. A005644, A013922, A052442, A259862, A326786, A327082, A327101, A327112, A327113, A327126, A327227.

Sequence in context: A274672 A122399 A320096 * A188409 A109587 A067426

Adjacent sequences: A327195 A327196 A327197 * A327199 A327200 A327201

KEYWORD

nonn

AUTHOR

Gus Wiseman, Sep 01 2019

EXTENSIONS

Terms a(6) and beyond from Andrew Howroyd, Dec 26 2020

STATUS

approved