cp's OEIS Frontend

A327051 Vertex-connectivity of the set-system with BII-number n.

%I A327051 #7 Sep 02 2019 08:04:51
%S A327051 0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,1,1,0,0,1,1,1,1,1,1,0,0,1,1,1,1,1,0,
%T A327051 1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,2,2,2,2,1,1,1,1,2,2,2,2,2,2,2,2,
%U A327051 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2
%N A327051 Vertex-connectivity of the set-system with BII-number n.
%C A327051 A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every set-system (finite set of finite nonempty sets) has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges.
%C A327051 The vertex-connectivity of a set-system is the minimum number of vertices that must be removed (along with any empty or duplicate edges) to obtain a non-connected set-system or singleton. Except for cointersecting set-systems (A326853), this is the same as cut-connectivity (A326786).
%H A327051 Wikipedia, <a href="https://en.wikipedia.org/wiki/K-vertex-connected_graph">k-vertex-connected graph</a>
%e A327051 Positions of first appearances of each integer, together with the corresponding set-systems, are:
%e A327051      0: {}
%e A327051      4: {{1,2}}
%e A327051     52: {{1,2},{1,3},{2,3}}
%e A327051   2868: {{1,2},{1,3},{2,3},{1,4},{2,4},{3,4}}
%t A327051 bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
%t A327051 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]]]]]]]]];
%t A327051 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]}]]
%t A327051 Table[vertConnSys[Union@@bpe/@bpe[n],bpe/@bpe[n]],{n,0,100}]
%Y A327051 Cut-connectivity is A326786.
%Y A327051 Spanning edge-connectivity is A327144.
%Y A327051 Non-spanning edge-connectivity is A326787.
%Y A327051 The enumeration of labeled graphs by vertex-connectivity is A327334.
%Y A327051 Cf. A000120, A013922, A029931, A048793, A070939, A259862, A322389, A323818, A326031, A327125, A327198, A327336.
%K A327051 nonn
%O A327051 0,53
%A A327051 _Gus Wiseman_, Sep 02 2019