A327051 - OEIS

%I #7 Sep 02 2019 08:04:51

%S 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 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 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2

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

%C 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 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 Wikipedia, <a href="https://en.wikipedia.org/wiki/K-vertex-connected_graph">k-vertex-connected graph</a>

%e Positions of first appearances of each integer, together with the corresponding set-systems, are:

%e      0: {}

%e      4: {{1,2}}

%e     52: {{1,2},{1,3},{2,3}}

%e   2868: {{1,2},{1,3},{2,3},{1,4},{2,4},{3,4}}

%t bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];

%t 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 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 Table[vertConnSys[Union@@bpe/@bpe[n],bpe/@bpe[n]],{n,0,100}]

%Y Cut-connectivity is A326786.

%Y Spanning edge-connectivity is A327144.

%Y Non-spanning edge-connectivity is A326787.

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

%Y Cf. A000120, A013922, A029931, A048793, A070939, A259862, A322389, A323818, A326031, A327125, A327198, A327336.

%K nonn

%O 0,53

%A _Gus Wiseman_, Sep 02 2019