|
%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
|
