A327198 -id:A327198 - cp's OEIS frontend

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

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

Gus Wiseman, Aug 25 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 and no edges has cut-connectivity 1. Except for complete graphs, this is the same as vertex-connectivity.

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

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.

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

a(21)-a(27) from Robert Price, May 20 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}]

A052443 Number of simple unlabeled n-node graphs of connectivity 2.

Original entry on oeis.org

0, 0, 1, 2, 7, 39, 332, 4735, 113176, 4629463, 327695586, 40525166511, 8850388574939, 3453378695335727, 2435485662537561705, 3137225298932374490227, 7448146273273417700880931, 32837456713651735794742705141, 270528237651574516777595556494978, 4186091025846007046878947026003803389

Offset: 1

Eric W. Weisstein

nonn

Jean-François Alcover, Table of n, a(n) for n = 1..23
Jens M. Schmidt, Data files in graph6 format
Eric Weisstein's World of Mathematics, k-Connected Graph.
Gus Wiseman, The a(5) = 7 graphs with vertex-connectivity 2.

Column k=2 of A259862.
Cf. A000719, A002218, A006290, A052442, A052444, A052445.
The labeled version is A327198.
2-vertex-connected graphs are A013922.
Cf. A322387, A327051, A327101, A327334.

A002218 = Cases[Import["https://oeis.org/A002218/b002218.txt", "Table"], {, }][[All, 2]];
A006290 = Cases[Import["https://oeis.org/A006290/b006290.txt", "Table"], {, }][[All, 2]];
a[1] = 0; a[2] = 0; a[3] = 1;
a[n_] := A002218[[n]] - A006290[[n-3]];
Array[a, 23] (* Jean-François Alcover, Jan 07 2021, after Andrew Howroyd *)

a(n) = A002218(n) - A006290(n) for n > 2. - Andrew Howroyd, Sep 04 2019

Name clarified and a(8)-a(11) by Jens M. Schmidt, Feb 18 2019
a(2)-a(3) corrected by Andrew Howroyd, Aug 28 2019
a(12)-a(20) from Andrew Howroyd, Sep 04 2019

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

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

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A052443 Number of simple unlabeled n-node graphs of connectivity 2.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica