A327375 Number of set-systems with n vertices and vertex-connectivity 2.

0, 0, 0, 72, 4752

Offset

0,4

Comments

A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. 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

Table of n, a(n) for n=0..4.

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], {1, n}]], vertConnSys[Range[n], #]==2&]], {n, 0, 3}]

Crossrefs

BII-numbers for vertex-connectivity 2 are A327374.

BII-numbers for cut-connectivity 2 are A327082.

BII-numbers for spanning edge-connectivity 2 are A327108.

BII-numbers for non-spanning edge-connectivity 2 are A327097.

Labeled graphs with vertex-connectivity 2 are A327198.

The vertex-connectivity of the set-system with BII-number n is A327051(n).

The enumeration of labeled graphs by vertex-connectivity is A327334.

Cf. A013922, A259862, A322389, A322390, A323818, A327336.

Sequence in context: A238772 A225831 A286930 * A054557 A167871 A103861

Adjacent sequences: A327372 A327373 A327374 * A327376 A327377 A327378

Keyword

nonn,more

Author

Gus Wiseman, Sep 05 2019

Status

approved