A327336 -id:A327336 - 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

A327051 Vertex-connectivity of the set-system with BII-number n.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2

Offset: 0

Gus Wiseman, Sep 02 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.

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. Except for cointersecting set-systems (A326853), this is the same as cut-connectivity (A326786).

			Positions of first appearances of each integer, together with the corresponding set-systems, are:
     0: {}
     4: {{1,2}}
    52: {{1,2},{1,3},{2,3}}
  2868: {{1,2},{1,3},{2,3},{1,4},{2,4},{3,4}}

Wikipedia, k-vertex-connected graph

Cut-connectivity is A326786.
Spanning edge-connectivity is A327144.
Non-spanning edge-connectivity is A326787.
The enumeration of labeled graphs by vertex-connectivity is A327334.
Cf. A000120, A013922, A029931, A048793, A070939, A259862, A322389, A323818, A326031, A327125, A327198, A327336.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
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[vertConnSys[Union@@bpe/@bpe[n],bpe/@bpe[n]],{n,0,100}]

A327114 Number of labeled simple graphs covering n vertices with cut-connectivity 1.

Original entry on oeis.org

0, 0, 0, 3, 28, 490, 15336, 851368, 85010976, 15615858960, 5388679220480, 3548130389657216, 4507988483733389568, 11145255551131555572992, 53964198507018134569758720, 514158235191699333805861463040

Offset: 0

Gus Wiseman, Aug 25 2019

nonn

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

Andrew Howroyd, Table of n, a(n) for n = 0..50

Column k = 1 of A327126.
The unlabeled version is A052442, if we assume A052442(2) = 0.
Connected non-separable graphs are A013922.
BII-numbers for cut-connectivity 1 are A327098.
Set-systems with cut-connectivity 1 are counted by A327197.
Labeled simple graphs with vertex-connectivity 1 are A327336.
Cf. A001187, A054592, A259862, A322389, A322390, A326786, A327070, A327100, A327125.

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}]],Union@@#==Range[n]&&cutConnSys[Range[n],#]==1&]],{n,0,3}]

seq(n)={my(g=log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n))); Vec(serlaplace(g-intformal(1+log(x/serreverse(x*deriv(g))))), -(n+1))} \\ Andrew Howroyd, Sep 11 2019

a(n) = A001187(n) - A013922(n), if we assume A001187(1) = 0.

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

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

A327335 Number of non-isomorphic set-systems with n vertices and at least one endpoint/leaf.

Original entry on oeis.org

0, 1, 4, 18, 216

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. A leaf is an edge containing a vertex that does not belong to any other edge, while an endpoint is a vertex belonging to only one edge.

Also covering set-systems with minimum covered vertex-degree 1.

			Non-isomorphic representatives of the a(1) = 1 through a(3) = 18 set-systems:
  {{1}}  {{1}}        {{1}}
         {{1,2}}      {{1,2}}
         {{1},{2}}    {{1},{2}}
         {{1},{1,2}}  {{1,2,3}}
                      {{1},{1,2}}
                      {{1},{2,3}}
                      {{1},{1,2,3}}
                      {{1,2},{1,3}}
                      {{1},{2},{3}}
                      {{1,2},{1,2,3}}
                      {{1},{2},{1,3}}
                      {{1},{1,2},{1,3}}
                      {{1},{1,2},{2,3}}
                      {{1},{2},{1,2,3}}
                      {{1},{1,2},{1,2,3}}
                      {{1},{2},{3},{1,2}}
                      {{1},{2},{1,2},{1,3}}
                      {{1},{2},{1,2},{1,2,3}}

Unlabeled set-systems are A000612.
The labeled version is A327228.
The covering version is A327230 (first differences).
Cf. A002494, A245797, A261919, A283877, A327103, A327105, A327197, A327227, A327229, A327336.

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.

A327356 Number of connected separable antichains of nonempty sets covering n vertices (vertex-connectivity 1).

Original entry on oeis.org

0, 0, 1, 3, 40, 1365

Offset: 0

Gus Wiseman, Sep 11 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 resulting empty edges) to obtain a non-connected set-system or singleton. Note that this means a single node has vertex-connectivity 0.

			Non-isomorphic representatives of the a(4) = 40 set-systems:
  {{1,2},{1,3,4}}
  {{1,2},{1,3},{1,4}}
  {{1,2},{1,3},{2,4}}
  {{1,2},{1,3},{1,4},{2,3}}

Column k = 1 of A327351.
The graphical case is A327336.
The unlabeled version is A327436.
Cf. A014466, A048143, A307249, A326786, A326950, A327062, A327112, A327114, A327334.

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

A327374 BII-numbers of set-systems with vertex-connectivity 2.

Original entry on oeis.org

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, 108, 109, 110, 111, 112, 113, 114, 115, 116

Offset: 1

Gus Wiseman, Sep 04 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.

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.

			The sequence of all set-systems with vertex-connectivity 2 together with their BII-numbers begins:
  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}}
  64: {{1,2,3}}
  65: {{1},{1,2,3}}
  66: {{2},{1,2,3}}
  67: {{1},{2},{1,2,3}}
  68: {{1,2},{1,2,3}}
  69: {{1},{1,2},{1,2,3}}
  70: {{2},{1,2},{1,2,3}}
  71: {{1},{2},{1,2},{1,2,3}}
  72: {{3},{1,2,3}}
  73: {{1},{3},{1,2,3}}
  74: {{2},{3},{1,2,3}}
  75: {{1},{2},{3},{1,2,3}}

Positions of 2's in A327051.
Cut-connectivity 2 is A327082.
Spanning edge-connectivity 2 is A327108.
Non-spanning edge-connectivity 2 is A327097.
Vertex-connectivity 3 is A327376.
Labeled graphs with vertex-connectivity 2 are A327198.
Set-systems with vertex-connectivity 2 are A327375.
The enumeration of labeled graphs by vertex-connectivity is A327334.
Cf. A000120, A013922, A048793, A070939, A259862, A326031, A326749, A327336.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
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]}]];
Select[Range[0,200],vertConnSys[Union@@bpe/@bpe[#],bpe/@bpe[#]]==2&]

A327375 Number of set-systems with n vertices and vertex-connectivity 2.

Original entry on oeis.org

0, 0, 0, 72, 4752

Offset: 0

Gus Wiseman, Sep 05 2019

A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. 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.

BII-numbers for vertex-connectivity 2 are A327374.
BII-numbers for cut-connectivity 2 are A327082.
BII-numbers for spanning edge-connectivity 2 are A327108.
BII-numbers for non-spanning edge-connectivity 2 are A327097.
Labeled graphs with vertex-connectivity 2 are A327198.
The vertex-connectivity of the set-system with BII-number n is A327051(n).
The enumeration of labeled graphs by vertex-connectivity is A327334.
Cf. A013922, A259862, A322389, A322390, A323818, 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]]]]]]]]];
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],{1,n}]],vertConnSys[Range[n],#]==2&]],{n,0,3}]

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

A327051 Vertex-connectivity of the set-system with BII-number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A327114 Number of labeled simple graphs covering n vertices with cut-connectivity 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

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

A327335 Number of non-isomorphic set-systems with n vertices and at least one endpoint/leaf.

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

A327356 Number of connected separable antichains of nonempty sets covering n vertices (vertex-connectivity 1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327374 BII-numbers of set-systems with vertex-connectivity 2.

Views

Author

Keywords