A327113 -id:A327113 - cp's OEIS frontend

A327082 BII-numbers of set-systems with cut-connectivity 2.

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

Offset: 1

Gus Wiseman, Aug 20 2019

nonn

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).

			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}}.

Positions of 2's in A326786.
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.
Cf. A000120, A002218, A013922, A048793, A259862, A322387, A322388, A326031, A327041, A327114.

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&]

A327101 BII-numbers of 2-cut-connected set-systems (cut-connectivity >= 2).

Original entry on oeis.org

4, 5, 6, 7, 16, 17, 24, 25, 32, 34, 40, 42, 52, 53, 54, 55, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107

Offset: 1

Gus Wiseman, Aug 22 2019

nonn

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.

A set-system is 2-cut-connected if any single vertex can be removed (along with any empty edges) without making the set-system disconnected or empty. Except for cointersecting set-systems (A326853), this is the same as 2-vertex-connectivity.

			The sequence of all 2-cut-connected set-systems 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}}
  52: {{1,2},{1,3},{2,3}}
  53: {{1},{1,2},{1,3},{2,3}}
  54: {{2},{1,2},{1,3},{2,3}}
  55: {{1},{2},{1,2},{1,3},{2,3}}
  60: {{1,2},{3},{1,3},{2,3}}
  61: {{1},{1,2},{3},{1,3},{2,3}}
  62: {{2},{1,2},{3},{1,3},{2,3}}
  63: {{1},{2},{1,2},{3},{1,3},{2,3}}

Positions of numbers >= 2 in A326786.
2-cut-connected graphs are counted by A013922, if we assume A013922(2) = 0.
2-cut-connected integer partitions are counted by A322387.
BII-numbers for cut-connectivity 2 are A327082.
BII-numbers for cut-connectivity 1 are A327098.
BII-numbers for non-spanning edge-connectivity >= 2 are A327102.
BII-numbers for spanning edge-connectivity >= 2 are A327109.
Covering 2-cut-connected set-systems are counted by A327112.
Covering set-systems with cut-connectivity 2 are counted by A327113.
The labeled cut-connectivity triangle is A327125, with unlabeled version A327127.
Cf. A000120, A002218, A048793, A070939, A259862, A322388, A326031, A326749, A327097, A327108.

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]]]]]]]]];
cutConnSys[vts_,eds_]:=If[Length[vts]==1,1,Min@@Length/@Select[Subsets[vts],Function[del,csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]]];
Select[Range[0,100],cutConnSys[Union@@bpe/@bpe[#],bpe/@bpe[#]]>=2&]

If (*) is intersection and (-) is complement, we have A327101 * A326704 = A326751 - A058891, i.e., the intersection of A327101 (this sequence) with A326704 (antichains) is the complement of A058891 (singletons) in A326751 (blobs).

A327112 Number of set-systems covering n vertices with cut-connectivity >= 2, or 2-cut-connected set-systems.

Original entry on oeis.org

0, 0, 4, 72, 29856

Offset: 0

Gus Wiseman, Aug 24 2019

A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. The cut-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 disconnected or empty set-system. Except for cointersecting set-systems (A327040), this is the same as vertex-connectivity (A327334, A327051).

			Non-isomorphic representatives of the a(3) = 72 set-systems:
  {{123}}
  {{3}{123}}
  {{23}{123}}
  {{2}{3}{123}}
  {{1}{23}{123}}
  {{3}{23}{123}}
  {{12}{13}{23}}
  {{13}{23}{123}}
  {{1}{2}{3}{123}}
  {{1}{3}{23}{123}}
  {{2}{3}{23}{123}}
  {{3}{12}{13}{23}}
  {{2}{13}{23}{123}}
  {{3}{13}{23}{123}}
  {{12}{13}{23}{123}}
  {{1}{2}{3}{23}{123}}
  {{2}{3}{12}{13}{23}}
  {{1}{2}{13}{23}{123}}
  {{2}{3}{13}{23}{123}}
  {{3}{12}{13}{23}{123}}
  {{1}{2}{3}{12}{13}{23}}
  {{1}{2}{3}{13}{23}{123}}
  {{2}{3}{12}{13}{23}{123}}
  {{1}{2}{3}{12}{13}{23}{123}}

Covering 2-cut-connected graphs are A013922, if we assume A013922(2) = 1.
Covering 1-cut-connected antichains (clutters) are A048143, if we assume A048143(0) = A048143(1) =0.
Covering 2-cut-connected antichains (blobs) are A275307, if we assume A275307(1) = 0.
Covering set-systems with cut-connectivity 2 are A327113.
2-vertex-connected integer partitions are A322387.
BII-numbers of set-systems with cut-connectivity >= 2 are A327101.
The cut-connectivity of the set-system with BII-number n is A326786(n).
Cf. A002218, A003465, A013922, A259862, A323818, A327082, A327126, A327130.

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]]]]]]]]];
vConn[sys_]:=If[Length[csm[sys]]!=1,0,Min@@Length/@Select[Subsets[Union@@sys],Function[del,Length[csm[DeleteCases[DeleteCases[sys,Alternatives@@del,{2}],{}]]]!=1]]];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&vConn[#]>=2&]],{n,0,3}]

A327127 Triangle read by rows where T(n,k) is the number of unlabeled simple graphs with n vertices where k is the minimum number of vertices that must be removed (along with any incident edges) to obtain a disconnected or empty graph.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 5, 3, 2, 0, 1, 13, 11, 7, 2, 0, 1

Offset: 0

Gus Wiseman, Aug 25 2019

A graph with one vertex and no edges is considered to be connected. Except for complete graphs, this is the same as vertex-connectivity (A259862).

There are two ways to define (vertex) connectivity: the minimum size of a vertex cut, and the minimum of the maximum number of internally disjoint paths between two distinct vertices. For non-complete graphs they coincide, which is tremendously useful. For complete graphs with at least 2 vertices, there are no cuts but the second method still works so it is customary to use it to justify the connectivity of K_n being n-1. - Brendan McKay, Aug 28 2019.

			Triangle begins:
   1
   0  1
   1  0  1
   2  1  0  1
   5  3  2  0  1
  13 11  7  2  0  1

Brendan McKay, confusion over k-connected graphs, posting to Sequence Fans Mailing List, Jul 08 2015.

Row sums are A000088.
Column k = 0 is A000719, if we assume A000719(0) = 1.
Column k = 1 is A052442, if we assume A052442(1) = 1 and A052442(2) = 0.
The labeled version is A327125.
A more standard version (zeros removed) is A259862.
Cf. A052443, A322389, A326786, A327082, A327098, A327100, A327113, A327126, A327128, A327197.

A327197 Number of set-systems covering n vertices with cut-connectivity 1.

Original entry on oeis.org

0, 1, 0, 24, 1984

Offset: 0

Gus Wiseman, Sep 01 2019

A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. The cut-connectivity of a set-system is the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain in a disconnected or empty set-system. Except for cointersecting set-systems (A327040), this is the same as vertex-connectivity.

			The a(3) = 24 set-systems:
  {12}{13}  {1}{12}{13}  {1}{2}{12}{13}  {1}{2}{3}{12}{13}
  {12}{23}  {1}{12}{23}  {1}{2}{12}{23}  {1}{2}{3}{12}{23}
  {13}{23}  {1}{13}{23}  {1}{2}{13}{23}  {1}{2}{3}{13}{23}
            {2}{12}{13}  {1}{3}{12}{13}
            {2}{12}{23}  {1}{3}{12}{23}
            {2}{13}{23}  {1}{3}{13}{23}
            {3}{12}{13}  {2}{3}{12}{13}
            {3}{12}{23}  {2}{3}{12}{23}
            {3}{13}{23}  {2}{3}{13}{23}

The BII-numbers of these set-systems are A327098.
The same for cut-connectivity 2 is A327113.
The non-covering version is A327128.
Cf. A003465, A052442, A052443, A259862, A323818, A326786, A327101, A327112, A327114, A327126, A327229.

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]]]]]]]]];
cutConnSys[vts_,eds_]:=If[Length[vts]==1,1,Min@@Length/@Select[Subsets[vts],Function[del,csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]]];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&cutConnSys[Range[n],#]==1&]],{n,0,3}]

Inverse binomial transform of A327128.

A327198 Number of labeled simple graphs covering n vertices with vertex-connectivity 2.

Original entry on oeis.org

0, 0, 0, 1, 9, 212, 9600, 789792, 114812264, 29547629568, 13644009626400, 11489505388892800, 17918588321874717312, 52482523149603539181312, 292311315623259148521270784, 3129388799344153886272170009600, 64965507855114369076680860799267840

Offset: 0

Gus Wiseman, Sep 01 2019

nonn

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.

Andrew Howroyd, Table of n, a(n) for n = 0..25
Gus Wiseman, The a(4) = 9 simple covering graphs with vertex-connectivity 2.

The unlabeled version is A052443.

Cf. A005644, A013922, A052442, A259862, A326786, A327082, A327101, A327112, A327113, A327126, A327227.

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]]]]]]]]];
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]}]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],vertConnSys[Range[n],#]==2&]],{n,0,5}]

a(n) = A013922(n) - A005644(n) for n >= 3. - Andrew Howroyd, Dec 26 2020

Terms a(6) and beyond from Andrew Howroyd, Dec 26 2020

A327128 Number of set-systems with n vertices whose edge-set has cut-connectivity 1.

Original entry on oeis.org

0, 1, 2, 27, 2084

Offset: 0

Gus Wiseman, Sep 02 2019

A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. We define the cut-connectivity (A326786, A327237, A327126) 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 has cut-connectivity 1. Except for cointersecting set-systems (A326853, A327039, A327040), this is the same as vertex-connectivity (A327334, A327051).

The covering version is A327197.
The BII-numbers of these set-systems are A327098.
Cf. A003465, A052442, A052443, A259862, A323818, A326786, A327101, A327112, A327113, A327114, A327126, A327229.

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]]]]]]]]];
cutConnSys[vts_,eds_]:=If[Length[vts]==1,1,Min@@Length/@Select[Subsets[vts],Function[del,csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]]];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],cutConnSys[Union@@#,#]==1&]],{n,0,3}]

Binomial transform of A327197.

cp's OEIS Frontend

A327082 BII-numbers of set-systems with cut-connectivity 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327101 BII-numbers of 2-cut-connected set-systems (cut-connectivity >= 2).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A327112 Number of set-systems covering n vertices with cut-connectivity >= 2, or 2-cut-connected set-systems.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327127 Triangle read by rows where T(n,k) is the number of unlabeled simple graphs with n vertices where k is the minimum number of vertices that must be removed (along with any incident edges) to obtain a disconnected or empty graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A327197 Number of set-systems covering n vertices with cut-connectivity 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A327198 Number of labeled simple graphs covering n vertices with vertex-connectivity 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A327128 Number of set-systems with n vertices whose edge-set has cut-connectivity 1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula