login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

BII-numbers of set-systems with vertex-connectivity 2.
2

%I #4 Sep 09 2019 12:05:13

%S 52,53,54,55,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,

%T 79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,

%U 101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116

%N BII-numbers of set-systems with vertex-connectivity 2.

%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 resulting empty edges) to obtain a non-connected set-system or singleton. Note that this means a single node has vertex-connectivity 0.

%e The sequence of all set-systems with vertex-connectivity 2 together with their BII-numbers begins:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

%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 Select[Range[0,200],vertConnSys[Union@@bpe/@bpe[#],bpe/@bpe[#]]==2&]

%Y Positions of 2's in A327051.

%Y Cut-connectivity 2 is A327082.

%Y Spanning edge-connectivity 2 is A327108.

%Y Non-spanning edge-connectivity 2 is A327097.

%Y Vertex-connectivity 3 is A327376.

%Y Labeled graphs with vertex-connectivity 2 are A327198.

%Y Set-systems with vertex-connectivity 2 are A327375.

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

%Y Cf. A000120, A013922, A048793, A070939, A259862, A326031, A326749, A327336.

%K nonn

%O 1,1

%A _Gus Wiseman_, Sep 04 2019