cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

A327126 Triangle read by rows where T(n,k) is the number of labeled simple graphs covering n vertices with cut-connectivity k.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 0, 3, 0, 1, 3, 28, 9, 0, 1, 40, 490, 212, 25, 0, 1, 745, 15336, 9600, 1692, 75, 0, 1
Offset: 0

Views

Author

Gus Wiseman, Aug 25 2019

Keywords

Comments

We define the cut-connectivity of a graph to be the minimum number of vertices that must be removed (along with any incident edges) to obtain a disconnected or empty graph, with the exception that a graph with one vertex and no edges has cut-connectivity 1. Except for complete graphs, this is the same as vertex-connectivity.

Examples

			Triangle begins:
   1
   0   0
   0   0   1
   0   3   0   1
   3  28   9   0   1
  40 490 212  25   0   1

Crossrefs

After the first column, same as A327125.
Column k = 0 is A327070.
Column k = 1 is A327114.
Row sums are A006129.
Different from A327069.
Row sums without the first column are A001187, if we assume A001187(0) = A001187(1) = 0.
Row sums without the first two columns are A013922.
Cf. A006125, A259862, A322389, A326786, A327114, A327127, A327198, A327237.

Programs

  • Mathematica
    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],{2}]],Union@@#==Range[n]&&cutConnSys[Range[n],#]==k&]],{n,0,4},{k,0,n}]

Extensions

a(21)-a(27) from Robert Price, May 20 2021

A327098 BII-numbers of set-systems with cut-connectivity 1.

Original entry on oeis.org

1, 2, 8, 20, 21, 22, 23, 28, 29, 30, 31, 36, 37, 38, 39, 44, 45, 46, 47, 48, 49, 50, 51, 56, 57, 58, 59, 128, 260, 261, 262, 263, 272, 273, 276, 277, 278, 279, 280, 281, 284, 285, 286, 287, 292, 293, 294, 295, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309
Offset: 1

Views

Author

Gus Wiseman, Aug 21 2019

Keywords

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

Examples

			The sequence of all set-systems with cut-connectivity 1 together with their BII-numbers begins:
   1: {{1}}
   2: {{2}}
   8: {{3}}
  20: {{1,2},{1,3}}
  21: {{1},{1,2},{1,3}}
  22: {{2},{1,2},{1,3}}
  23: {{1},{2},{1,2},{1,3}}
  28: {{1,2},{3},{1,3}}
  29: {{1},{1,2},{3},{1,3}}
  30: {{2},{1,2},{3},{1,3}}
  31: {{1},{2},{1,2},{3},{1,3}}
  36: {{1,2},{2,3}}
  37: {{1},{1,2},{2,3}}
  38: {{2},{1,2},{2,3}}
  39: {{1},{2},{1,2},{2,3}}
  44: {{1,2},{3},{2,3}}
  45: {{1},{1,2},{3},{2,3}}
  46: {{2},{1,2},{3},{2,3}}
  47: {{1},{2},{1,2},{3},{2,3}}
  48: {{1,3},{2,3}}

Crossrefs

A subset of A326749.
Positions of 1's in A326786.
BII-numbers for cut-connectivity 2 are A327082.
BII-numbers for non-spanning edge-connectivity 1 are A327099.
BII-numbers for spanning edge-connectivity 1 are A327111.
Integer partitions with cut-connectivity 1 are counted by A322390.
Labeled connected separable graphs are counted by A327114.
Connected separable set-systems are counted by A327197.
Cf. A000120, A048793, A070939, A322389, A326031, A327100, A327125.

Programs

  • 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[#]]==1&]

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

Original entry on oeis.org

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

Views

Author

Gus Wiseman, Aug 20 2019

Keywords

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

Examples

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

Crossrefs

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.

Programs

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

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

Views

Author

Gus Wiseman, Sep 02 2019

Keywords

Comments

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

Crossrefs

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.

Programs

  • Mathematica
    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}]

Formula

Binomial transform of A327197.
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.