A327350 -id:A327350 - cp's OEIS frontend

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

1, 1, 0, 1, 1, 0, 4, 3, 1, 0, 26, 28, 9, 1, 0, 296, 490, 212, 25, 1, 0, 6064, 15336, 9600, 1692, 75, 1, 0, 230896, 851368, 789792, 210140, 14724, 231, 1, 0

Offset: 0

Gus Wiseman, Sep 01 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. Except for complete graphs, this is the same as cut-connectivity (A327125).

			Triangle begins:
    1
    1   0
    1   1   0
    4   3   1   0
   26  28   9   1   0
  296 490 212  25   1   0

Wikipedia, k-vertex-connected graph

The unlabeled version is A259862.
Row sums are A006125.
Column k = 0 is A054592, if we assume A054592(0) = A054592(1) = 1.
Column k = 1 is A327336.
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, if we assume A013922(1) = 0.
Cut-connectivity is A327125.
Spanning edge-connectivity is A327069.
Non-spanning edge-connectivity is A327148.
Cf. A322389, A327051, A327070, A327126, A327127, A327350.

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

a(21)-a(35) from Robert Price, May 14 2021

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

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 4, 3, 2, 0, 30, 40, 27, 17, 0, 546, 1365, 1842, 1690, 1451, 0, 41334

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
    1    1    0
    4    3    2    0
   30   40   27   17    0
  546 1365 1842 1690 1451    0

Row sums are A307249, or A006126 if empty edges are allowed.
Column k = 0 is A120338, if we assume A120338(0) = A120338(1) = 1.
Column k = 1 is A327356.
Column k = n - 1 is A327020.
The unlabeled version is A327359.
The version for vertex-connectivity >= k is A327350.
The version for spanning edge-connectivity is A327352.
The version for non-spanning edge-connectivity is A327353, with covering case A327357.
Cf. A003465, A006126, A014466, A048143, A293993, A323818, A326704, A327125, A327334, A327336.

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 28 2021

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

Original entry on oeis.org

1, 1, 0, 2, 1, 0, 5, 3, 2, 0, 20, 14, 10, 6, 0, 180, 157, 128, 91, 54, 0

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
    5   3   2   0
   20  14  10   6   0
  180 157 128  91  54   0
Non-isomorphic representatives of the antichains counted in row n = 4:
  {1234}          {1234}           {1234}           {1234}
  {1}{234}        {12}{134}        {123}{124}       {12}{134}{234}
  {12}{34}        {123}{124}       {12}{13}{234}    {123}{124}{134}
  {12}{134}       {12}{13}{14}     {12}{134}{234}   {12}{13}{14}{234}
  {123}{124}      {12}{13}{24}     {123}{124}{134}  {123}{124}{134}{234}
  {1}{2}{34}      {12}{13}{234}    {12}{13}{24}{34} {12}{13}{14}{23}{24}{34}
  {2}{13}{14}     {12}{134}{234}   {12}{13}{14}{234}
  {12}{13}{14}    {123}{124}{134}  {12}{13}{14}{23}{24}
  {12}{13}{24}    {12}{13}{14}{23} {123}{124}{134}{234}
  {1}{2}{3}{4}    {12}{13}{24}{34} {12}{13}{14}{23}{24}{34}
  {12}{13}{234}   {12}{13}{14}{234}
  {12}{134}{234}  {12}{13}{14}{23}{24}
  {123}{124}{134} {123}{124}{134}{234}
  {4}{12}{13}{23} {12}{13}{14}{23}{24}{34}
  {12}{13}{14}{23}
  {12}{13}{24}{34}
  {12}{13}{14}{234}
  {12}{13}{14}{23}{24}
  {123}{124}{134}{234}
  {12}{13}{14}{23}{24}{34}

Column k = 0 is A261005, or A006602 if empty edges are allowed.
Column k = 1 is A261006 (clutters), if we assume A261006(0) = A261006(1) = 0.
Column k = 2 is A305028 (blobs), if we assume A305028(0) = A305028(2) = 0.
Column k = n - 1 is A327425 (cointersecting).
The labeled version is A327350.
Negated first differences of rows are A327359.
Cf. A006126, A055621, A120338, A293606, A293993, A327334, A327351, A327356.

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.

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

A327436 Number of connected, unlabeled antichains of nonempty subsets of {1..n} covering n vertices with at least one cut-vertex (vertex-connectivity 1).

Original entry on oeis.org

0, 0, 1, 1, 4, 29

Offset: 0

Gus Wiseman, Sep 11 2019

nonn

			Non-isomorphic representatives of the a(2) = 1 through a(5) = 29 antichains:
  {12}  {12}{13}  {12}{134}         {12}{1345}
                  {12}{13}{14}      {123}{145}
                  {12}{13}{24}      {12}{13}{145}
                  {12}{13}{14}{23}  {12}{13}{245}
                                    {13}{24}{125}
                                    {13}{124}{125}
                                    {14}{123}{235}
                                    {12}{13}{14}{15}
                                    {12}{13}{14}{25}
                                    {12}{13}{24}{35}
                                    {12}{13}{14}{235}
                                    {12}{13}{23}{145}
                                    {12}{13}{45}{234}
                                    {12}{14}{23}{135}
                                    {12}{15}{134}{234}
                                    {15}{23}{124}{134}
                                    {15}{123}{124}{134}
                                    {15}{123}{124}{234}
                                    {12}{13}{14}{15}{23}
                                    {12}{13}{14}{23}{25}
                                    {12}{13}{14}{23}{45}
                                    {12}{13}{15}{24}{34}
                                    {12}{13}{14}{15}{234}
                                    {12}{13}{14}{25}{234}
                                    {12}{13}{14}{15}{23}{24}
                                    {12}{13}{14}{15}{23}{45}
                                    {12}{13}{14}{23}{24}{35}
                                    {15}{123}{124}{134}{234}
                                    {12}{13}{14}{15}{23}{24}{34}

Column k = 1 of A327359.
The labeled version is A327356.
Cf. A006602, A014466, A048143, A261005, A326704, A326786, A327112, A327114, A327426, A327334, A327336, A327350, A327351, A327358.

a(n > 2) = A261006(n) - A305028(n).

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

Original entry on oeis.org

1, 2, 0, 4, 1, 0, 9, 3, 2, 0, 29, 14, 10, 6, 0, 209, 157, 128, 91, 54, 0

Offset: 0

Gus Wiseman, Sep 26 2019

An antichain is a set of 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
    4   1   0
    9   3   2   0
   29  14  10   6   0
  209 157 128  91  54   0

Column k = 0 is A306505.
Column k = 1 is A261006 (clutters), if we assume A261006(0) = A261006(1) = 0.
Column k = 2 is A305028 (blobs), if we assume A305028(0) = A305028(2) = 0.
Except for the first column, same as A327358 (the covering case).
The labeled version is A327806.
Cf. A014466, A293606, A326704, A326950, A327062, A327334, A327350, A327351, A327805, A327808.

cp's OEIS Frontend

A327334 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

Links

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

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

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

A327436 Number of connected, unlabeled antichains of nonempty subsets of {1..n} covering n vertices with at least one cut-vertex (vertex-connectivity 1).

Views

Author

Keywords

Examples

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs