A327125 -id:A327125 - cp's OEIS frontend

A327149 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of simple labeled graphs covering n vertices with non-spanning edge-connectivity k.

1, 0, 1, 0, 0, 3, 1, 3, 12, 15, 10, 1, 40, 180, 297, 180, 60, 10, 1

Offset: 0

Gus Wiseman, Aug 27 2019

The non-spanning edge-connectivity of a graph is the minimum number of edges that must be removed (along with any non-covered vertices) to obtain a disconnected or empty graph.

			Triangle begins:
   1
   {}
   0   1
   0   0   3   1
   3  12  15  10   1
  40 180 297 180  60  10   1

Row sums are A006129.
Column k = 0 is A327070.
Column k = 1 is A327079.
The corresponding triangle for vertex-connectivity is A327126.
The corresponding triangle for spanning edge-connectivity is A327069.
The non-covering version is A327148.
The unlabeled version is A327201.
Cf. A001187, A263296, A322338, A322395, A326787, A327097, A327099, A327102, A327125, A327129, A327144.

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]]]]]]]]];
eConn[sys_]:=If[Length[csm[sys]]!=1,0,Length[sys]-Max@@Length/@Select[Union[Subsets[sys]],Length[csm[#]]!=1&]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&eConn[#]==k&]],{n,0,4},{k,0,Binomial[n,2]}]//.{foe___,0}:>{foe}

A327148(n,k) = Sum_{m = 0..n} binomial(n,m) T(m,k). In words, column k is the inverse binomial transform of column k of A327148.

A327350 Triangle read by rows where T(n,k) is the number of antichains of nonempty sets covering n vertices with vertex-connectivity >= k.

Original entry on oeis.org

1, 1, 0, 2, 1, 0, 9, 5, 2, 0, 114, 84, 44, 17, 0, 6894, 6348, 4983, 3141, 1451, 0, 7785062

Offset: 0

Gus Wiseman, Sep 09 2019

An antichain is a set of sets, none of which is a subset of any other. It is covering if there are no isolated vertices.
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. Note that this means a single node has vertex-connectivity 0.
If empty edges are allowed, we have T(0,0) = 2.

			Triangle begins:
     1
     1    0
     2    1    0
     9    5    2    0
   114   84   44   17    0
  6894 6348 4983 3141 1451    0
The antichains counted in row n = 3:
  {123}         {123}         {123}
  {1}{23}       {12}{13}      {12}{13}{23}
  {2}{13}       {12}{23}
  {3}{12}       {13}{23}
  {12}{13}      {12}{13}{23}
  {12}{23}
  {13}{23}
  {1}{2}{3}
  {12}{13}{23}

Column k = 0 is A307249, or A006126 if empty edges are allowed.
Column k = 1 is A048143 (clutters), if we assume A048143(0) = A048143(1) = 0.
Column k = 2 is A275307 (blobs), if we assume A275307(1) = A275307(2) = 0.
Column k = n - 1 is A327020 (cointersecting antichains).
The unlabeled version is A327358.
Negated first differences of rows are A327351.
BII-numbers of antichains are A326704.
Antichain covers are A006126.
Cf. A003465, A014466, A120338, A293606, A293993, A319639, A323818, A327112, A327125, A327334, A327336, A327352, A327356, A327357, A327358.

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]]]]]]]]];
stableSets[u_,Q_]:=If[Length[u]==0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q]]]];
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[stableSets[Subsets[Range[n],{1,n}],SubsetQ],Union@@#==Range[n]&&vertConnSys[Range[n],#]>=k&]],{n,0,4},{k,0,n}]

a(21) from Robert Price, May 24 2021

A327359 Triangle read by rows where T(n,k) is the number of unlabeled antichains of nonempty sets covering n vertices with vertex-connectivity exactly k.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 2, 1, 2, 0, 6, 4, 4, 6, 0, 23, 29, 37, 37, 54, 0

Offset: 0

Gus Wiseman, Sep 10 2019

An antichain is a set of sets, none of which is a subset of any other. It is covering if there are no isolated vertices.
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. Note that this means a single node has vertex-connectivity 0.
If empty edges are allowed, we have T(0,0) = 2.

			Triangle begins:
   1
   1  0
   1  1  0
   2  1  2  0
   6  4  4  6  0
  23 29 37 37 54  0
Row n = 4 counts the following antichains:
{1}{234}      {14}{234}        {134}{234}           {1234}
{12}{34}      {13}{24}{34}     {13}{14}{234}        {12}{134}{234}
{1}{2}{34}    {14}{24}{34}     {12}{13}{24}{34}     {124}{134}{234}
{1}{24}{34}   {14}{23}{24}{34} {13}{14}{23}{24}{34} {12}{13}{14}{234}
{1}{2}{3}{4}                                        {123}{124}{134}{234}
{1}{23}{24}{34}                                     {12}{13}{14}{23}{24}{34}

Row sums are A261005, or A006602 if empty edges are allowed.
Column k = 0 is A327426.
Column k = 1 is A327436.
Column k = n - 1 is A327425.
The labeled version is A327351.
Cf. A003465, A006126, A014466, A048143, A293993, A323818, A326704, A327125, A327334, A327336, A327350, A327358.

A327237 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices that, if the isolated vertices are removed, have cut-connectivity k.

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 1, 3, 3, 1, 4, 40, 15, 4, 1, 56, 660, 267, 35, 5, 1, 1031, 18756, 11022, 1862, 90, 6, 1

Offset: 0

Gus Wiseman, Sep 03 2019

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 has cut-connectivity 1. Except for complete graphs, this is the same as vertex-connectivity.

			Triangle begins:
   1
   1   0
   1   0   1
   1   3   3   1
   4  40  15   4   1
  56 660 267  35   5   1

Row sums are A006125.
Column k = 0 is A327199.
The covering case is A327126.
Row sums without the first column are A287689.
Cf. A006125, A001187, A013922, A259862, A322389, A326786, A327070, A327114, A327125, A327127, A327198.

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

Column-wise binomial transform of A327126.

a(21)-a(27) from Jinyuan Wang, Jun 27 2020

A327805 Triangle read by rows where T(n,k) is the number of unlabeled simple graphs with n vertices and vertex-connectivity >= k.

Original entry on oeis.org

1, 1, 0, 2, 1, 0, 4, 2, 1, 0, 11, 6, 3, 1, 0, 34, 21, 10, 3, 1, 0, 156, 112, 56, 17, 4, 1, 0, 1044, 853, 468, 136, 25, 4, 1, 0, 12346, 11117, 7123, 2388, 384, 39, 5, 1, 0, 274668, 261080, 194066, 80890, 14480, 1051, 59, 5, 1, 0, 12005168, 11716571, 9743542, 5114079, 1211735, 102630, 3211, 87, 6, 1, 0

Offset: 0

Gus Wiseman, Sep 26 2019

The vertex-connectivity of a graph is the minimum number of vertices that must be removed (along with any incident edges) to obtain a non-connected graph or singleton. Note that this means a single node has vertex-connectivity 0.

			Triangle begins:
   1
   1  0
   2  1  0
   4  2  1  0
  11  6  3  1  0
  34 21 10  3  1  0

Gus Wiseman, The graphs counted in row n = 4 (isolated vertices not shown).

Row-wise partial sums of A259862.
The labeled version is A327363.
The covering case is A327365, from which this sequence differs only in the k = 0 column.
Column k = 0 is A000088 (graphs).
Column k = 1 is A001349 (connected graphs), if we assume A001349(0) = A001349(1) = 0.
Column k = 2 is A002218 (2-connected graphs), if we assume A002218(2) = 0.
The triangle for vertex-connectivity exactly k is A259862.
Cf. A326786, A327051, A327114, A327125, A327126, A327127, A327334.

T(n,k) = Sum_{j=k..n} A259862(n,j).

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

A327806 Triangle read by rows where T(n,k) is the number of antichains of sets with n vertices and vertex-connectivity >= k.

Original entry on oeis.org

1, 2, 0, 5, 1, 0, 19, 5, 2, 0, 167, 84, 44, 17, 0

Offset: 0

Gus Wiseman, Sep 26 2019

An antichain is a set of nonempty sets, none of which is a subset of any other.

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.

			Triangle begins:
    1
    2   0
    5   1   0
   19   5   2   0
  167  84  44  17   0

Except for the first column, same as the covering case A327350.
Column k = 0 is A014466 (antichains).
Column k = 1 is A048143 (clutters), if we assume A048143(0) = A048143(1) = 0.
Column k = 2 is A275307 (blobs), if we assume A275307(1) = A275307(2) = 0.
The unlabeled version is A327807.
The case for vertex connectivity exactly k is A327351.
Cf. A014466, A293606, A326704, A327057, A327062, A327125, A327358.

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]]]]]]]]];
stableSets[u_,Q_]:=If[Length[u]==0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q]]]];
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[stableSets[Subsets[Range[n],{1,n}],SubsetQ],vertConnSys[Range[n],#]>=k&]],{n,0,4},{k,0,n}]

A327234 Smallest BII-number of a set-system with cut-connectivity n.

Original entry on oeis.org

0, 1, 4, 52, 2868

Offset: 0

Gus Wiseman, Sep 03 2019

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) 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), this is the same as vertex-connectivity (A327051).
Conjecture: a(n > 1) = A327373(n) = the BII-number of K_n.

			The sequence of terms together with their corresponding set-systems:
     0: {}
     1: {{1}}
     4: {{1,2}}
    52: {{1,2},{1,3},{2,3}}
  2868: {{1,2},{1,3},{2,3},{1,4},{2,4},{3,4}}

The same for spanning edge-connectivity is A327147.
The cut-connectivity of the set-system with BII-number n is A326786(n).
Cf. A000120, A002450, A029931, A048793, A070939, A259862, A326031, A327082, A327098, A327125, A327126, A327127, A327373.

A327363 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and vertex-connectivity >= k.

Original entry on oeis.org

1, 1, 0, 2, 1, 0, 8, 4, 1, 0, 64, 38, 10, 1, 0, 1024, 728, 238, 26, 1, 0

Offset: 0

Gus Wiseman, Sep 26 2019

The vertex-connectivity of a graph is the minimum number of vertices that must be removed (along with any incident edges) to obtain a non-connected graph or singleton.

			Triangle begins:
     1
     1    0
     2    1    0
     8    4    1    0
    64   38   10    1    0
  1024  728  238   26    1    0

Column k = 0 is A006125.
Column k = 1 is A001187.
Column k = 2 is A013922.
The unlabeled version is A327805.
Row-wise partial sums of A327334 (vertex-connectivity exactly k).
Cf. A259862, A327114, A327125, A327126, A327127, A327806.

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],#]>=k&]],{n,0,4},{k,0,n}]

cp's OEIS Frontend

A327149 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of simple labeled graphs covering n vertices with non-spanning edge-connectivity k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A327350 Triangle read by rows where T(n,k) is the number of antichains of nonempty sets covering n vertices with vertex-connectivity >= k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A327359 Triangle read by rows where T(n,k) is the number of unlabeled antichains of nonempty sets covering n vertices with vertex-connectivity exactly k.

Views

Author

Keywords

Comments

Examples

Crossrefs

A327237 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices that, if the isolated vertices are removed, have cut-connectivity k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A327805 Triangle read by rows where T(n,k) is the number of unlabeled simple graphs with n vertices and vertex-connectivity >= k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A327806 Triangle read by rows where T(n,k) is the number of antichains of sets with n vertices and vertex-connectivity >= k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327234 Smallest BII-number of a set-system with cut-connectivity n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A327363 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and vertex-connectivity >= k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica