|
|
A327082
|
|
BII-numbers of set-systems with cut-connectivity 2.
|
|
12
|
|
|
4, 5, 6, 7, 16, 17, 24, 25, 32, 34, 40, 42, 256, 257, 384, 385, 512, 514, 640, 642, 816, 817, 818, 819, 820, 821, 822, 823, 824, 825, 826, 827, 828, 829, 830, 831, 832, 833, 834, 835, 836, 837, 838, 839, 840, 841, 842, 843, 844, 845, 846, 847, 848, 849, 850
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
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.
We define the cut-connectivity (A326786, A327237), of a set-system to be the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain a disconnected or empty set-system, with the exception that a set-system with one vertex and no edges has cut-connectivity 1. Except for cointersecting set-systems (A326853, A327039), this is the same as vertex-connectivity (A327334, A327051).
|
|
LINKS
|
|
|
EXAMPLE
|
The sequence of all set-systems with cut-connectivity 2 together with their BII-numbers begins:
4: {{1,2}}
5: {{1},{1,2}}
6: {{2},{1,2}}
7: {{1},{2},{1,2}}
16: {{1,3}}
17: {{1},{1,3}}
24: {{3},{1,3}}
25: {{1},{3},{1,3}}
32: {{2,3}}
34: {{2},{2,3}}
40: {{3},{2,3}}
42: {{2},{3},{2,3}}
256: {{1,4}}
257: {{1},{1,4}}
384: {{4},{1,4}}
385: {{1},{4},{1,4}}
512: {{2,4}}
514: {{2},{2,4}}
640: {{4},{2,4}}
642: {{2},{4},{2,4}}
The first term involving an edge of size 3 is 832: {{1,2,3},{1,4},{2,4}}.
|
|
MATHEMATICA
|
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[OrderedQ[#], UnsameQ@@#, Length[Intersection@@s[[#]]]>0]&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
vertConnSys[sys_]:=If[Length[csm[sys]]!=1, 0, Min@@Length/@Select[Subsets[Union@@sys], Function[del, Length[csm[DeleteCases[DeleteCases[sys, Alternatives@@del, {2}], {}]]]!=1]]];
Select[Range[0, 100], vertConnSys[bpe/@bpe[#]]==2&]
|
|
CROSSREFS
|
BII-numbers for non-spanning edge-connectivity 2 are A327097.
BII-numbers for spanning edge-connectivity 2 are A327108.
The cut-connectivity 1 version is A327098.
The cut-connectivity > 1 version is A327101.
Covering 2-cut-connected set-systems are counted by A327112.
Covering set-systems with cut-connectivity 2 are counted by A327113.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|