A052443 -id:A052443 - cp's OEIS frontend

A259862 Triangle read by rows: T(n,k) = number of unlabeled graphs with n nodes and connectivity exactly k (n>=1, 0<=k<=n-1).

1, 1, 1, 2, 1, 1, 5, 3, 2, 1, 13, 11, 7, 2, 1, 44, 56, 39, 13, 3, 1, 191, 385, 332, 111, 21, 3, 1, 1229, 3994, 4735, 2004, 345, 34, 4, 1, 13588, 67014, 113176, 66410, 13429, 992, 54, 4, 1, 288597, 1973029, 4629463, 3902344, 1109105, 99419, 3124, 81, 5, 1, 12297299, 105731474, 327695586, 388624106, 162318088, 21500415, 820956, 9813, 121, 5, 1

Offset: 1

N. J. A. Sloane, Jul 08 2015

These are vertex-connectivities. Spanning edge-connectivity is A263296. Non-spanning edge-connectivity is A327236. Cut-connectivity is A327127. - Gus Wiseman, Sep 03 2019

			Triangle begins:
       1;
       1,       1;
       2,       1,       1;
       5,       3,       2,       1;
      13,      11,       7,       2,       1;
      44,      56,      39,      13,       3,     1;
     191,     385,     332,     111,      21,     3,    1;
    1229,    3994,    4735,    2004,     345,    34,    4,  1;
   13588,   67014,  113176,   66410,   13429,   992,   54,  4, 1;
  288597, 1973029, 4629463, 3902344, 1109105, 99419, 3124, 81, 5, 1;
  12297299,105731474,327695586,388624106,162318088,21500415,820956,9813,121,5,1;
  ...

Georg Grasegger, Table of n, a(n) for n = 1..78
Brendan McKay, confusion over k-connected graphs, posting to Sequence Fans Mailing List, Jul 08 2015.
Jens M. Schmidt, Combinatorial Data
Gus Wiseman, The graphs counted by row n = 5 (isolated vertices not shown).

Columns k=0..10 (up to initial nonzero terms) are A000719, A052442, A052443, A052444, A052445, A324234, A324235, A324088, A324089, A324090, A324091.
Row sums are A000088.
Number of graphs with connectivity at least k for k=1..10 are A001349, A002218, A006290, A086216, A086217, A324240, A324092, A324093, A324094, A324095.
The labeled version is A327334.
Cf. A002494, A263296, A322389, A326786, A327127, A327236.

A052442 Number of simple unlabeled n-node graphs of connectivity 1.

Original entry on oeis.org

0, 1, 1, 3, 11, 56, 385, 3994, 67014, 1973029, 105731474, 10439496931, 1902968718515, 641662974453892, 401490336727861176, 467924684115578671326, 1019752390010650509117288, 4171131179469162937375841939, 32134378048921787829834095722663, 467778894124037894839737804918978194

Offset: 1

Eric W. Weisstein

nonn

Jean-François Alcover, Table of n, a(n) for n = 1..26
Jens M. Schmidt, Data files in graph6 format
Eric Weisstein's World of Mathematics, k-Connected Graph.
Eric Weisstein's World of Mathematics, Biconnected Graph

Column k=1 of A259862.

Cf. A000719, A052443, A052444, A052445.

A001349 = Cases[Import["https://oeis.org/A001349/b001349.txt", "Table"], {, }][[All, 2]];
A002218 = Cases[Import["https://oeis.org/A002218/b002218.txt", "Table"], {, }][[All, 2]];
a[1] = 0; a[2] = 1;
a[n_] := A001349[[n+1]] - A002218[[n]];
Array[a, 26] (* Jean-François Alcover, Sep 10 2019, after Andrew Howroyd *)

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

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

A052445 Number of simple unlabeled n-node graphs of connectivity 4.

Original entry on oeis.org

0, 0, 0, 0, 1, 3, 21, 345, 13429, 1109105, 162318088, 39460518399

Offset: 1

Eric W. Weisstein

			The a(6) = 3 exactly-4-connected 6-node graphs are the complete graph K_6 with 1, 2, or 3 non-adjacent edges removed.

Brendan McKay, confusion over k-connected graphs, posting to Sequence Fans Mailing List, Jul 08 2015.
Jens M. Schmidt, Data files in graph6 format
Eric Weisstein's World of Mathematics, k-Connected Graph
Eric Weisstein's World of Mathematics, Vertex Connectivity

Cf. A052442, A052443, A052444, A086216, A086217, A259862.

a(n) = A086216(n) - A086217(n). - Andrey Zabolotskiy, Nov 20 2017

Partially edited by N. J. A. Sloane, Jul 08 2015 at the suggestion of Brendan McKay
a(8)-a(11) copied from A259862 by Andrey Zabolotskiy, Nov 20 2017
a(4)-a(5) corrected by Andrew Howroyd, Aug 28 2019
a(12) from Sean A. Irvine, Dec 12 2021

A327127 Triangle read by rows where T(n,k) is the number of unlabeled simple graphs with n vertices where k is the minimum number of vertices that must be removed (along with any incident edges) to obtain a disconnected or empty graph.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 5, 3, 2, 0, 1, 13, 11, 7, 2, 0, 1

Offset: 0

Gus Wiseman, Aug 25 2019

A graph with one vertex and no edges is considered to be connected. Except for complete graphs, this is the same as vertex-connectivity (A259862).

There are two ways to define (vertex) connectivity: the minimum size of a vertex cut, and the minimum of the maximum number of internally disjoint paths between two distinct vertices. For non-complete graphs they coincide, which is tremendously useful. For complete graphs with at least 2 vertices, there are no cuts but the second method still works so it is customary to use it to justify the connectivity of K_n being n-1. - Brendan McKay, Aug 28 2019.

			Triangle begins:
   1
   0  1
   1  0  1
   2  1  0  1
   5  3  2  0  1
  13 11  7  2  0  1

Brendan McKay, confusion over k-connected graphs, posting to Sequence Fans Mailing List, Jul 08 2015.

Row sums are A000088.
Column k = 0 is A000719, if we assume A000719(0) = 1.
Column k = 1 is A052442, if we assume A052442(1) = 1 and A052442(2) = 0.
The labeled version is A327125.
A more standard version (zeros removed) is A259862.
Cf. A052443, A322389, A326786, A327082, A327098, A327100, A327113, A327126, A327128, A327197.

A327197 Number of set-systems covering n vertices with cut-connectivity 1.

Original entry on oeis.org

0, 1, 0, 24, 1984

Offset: 0

Gus Wiseman, Sep 01 2019

A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. The cut-connectivity of a set-system is the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain in a disconnected or empty set-system. Except for cointersecting set-systems (A327040), this is the same as vertex-connectivity.

			The a(3) = 24 set-systems:
  {12}{13}  {1}{12}{13}  {1}{2}{12}{13}  {1}{2}{3}{12}{13}
  {12}{23}  {1}{12}{23}  {1}{2}{12}{23}  {1}{2}{3}{12}{23}
  {13}{23}  {1}{13}{23}  {1}{2}{13}{23}  {1}{2}{3}{13}{23}
            {2}{12}{13}  {1}{3}{12}{13}
            {2}{12}{23}  {1}{3}{12}{23}
            {2}{13}{23}  {1}{3}{13}{23}
            {3}{12}{13}  {2}{3}{12}{13}
            {3}{12}{23}  {2}{3}{12}{23}
            {3}{13}{23}  {2}{3}{13}{23}

The BII-numbers of these set-systems are A327098.
The same for cut-connectivity 2 is A327113.
The non-covering version is A327128.
Cf. A003465, A052442, A052443, A259862, A323818, A326786, A327101, A327112, A327114, A327126, A327229.

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

Inverse binomial transform of A327128.

A327198 Number of labeled simple graphs covering n vertices with vertex-connectivity 2.

Original entry on oeis.org

0, 0, 0, 1, 9, 212, 9600, 789792, 114812264, 29547629568, 13644009626400, 11489505388892800, 17918588321874717312, 52482523149603539181312, 292311315623259148521270784, 3129388799344153886272170009600, 64965507855114369076680860799267840

Offset: 0

Gus Wiseman, Sep 01 2019

nonn

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.

Andrew Howroyd, Table of n, a(n) for n = 0..25
Gus Wiseman, The a(4) = 9 simple covering graphs with vertex-connectivity 2.

The unlabeled version is A052443.

Cf. A005644, A013922, A052442, A259862, A326786, A327082, A327101, A327112, A327113, A327126, A327227.

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

a(n) = A013922(n) - A005644(n) for n >= 3. - Andrew Howroyd, Dec 26 2020

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

A052444 Number of simple unlabeled n-node graphs of connectivity 3.

Original entry on oeis.org

0, 0, 0, 1, 2, 13, 111, 2004, 66410, 3902344, 388624106, 65142804740

Offset: 1

Eric W. Weisstein

Jens M. Schmidt, Data files in graph6 format
Eric Weisstein's World of Mathematics, k-Connected Graph.

Column k=3 of A259862.

Cf. A000719, A006290, A052442, A052443, A052445, A086216.

a(n) = A006290(n) - A086216(n). - Andrew Howroyd, Sep 04 2019

Name edited and a(8)-a(11) by Jens M. Schmidt, Feb 18 2019
a(3)-a(4) corrected by Andrew Howroyd, Aug 28 2019
a(12) from Sean A. Irvine, Nov 28 2021

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

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

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.

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

Binomial transform of A327197.

A086217 Number of 5-connected graphs on n nodes.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 4, 39, 1051, 102630, 22331311, 8491843895

Offset: 1

Eric W. Weisstein, Jul 12 2003

Travis Hoppe and Anna Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
Jens M. Schmidt, Data files in graph6 format
Eric Weisstein's World of Mathematics, k-Connected Graph

Cf. A002218, A052443, A052445, A086216, A259862, A324234, A324240.

a(n) = A324240(n) + A324234(n). - Andrew Howroyd, Sep 04 2019

a(n) = A086216(n) - A052445(n). - Jean-François Alcover, Sep 13 2019, after Andrew Howroyd in A086216

Offset corrected by Travis Hoppe, Apr 11 2014
a(10) from the Encyclopedia of Finite Graphs (Travis Hoppe and Anna Petrone), Apr 11 2014
a(11) by Jens M. Schmidt, Feb 20 2019
a(12) added by Georg Grasegger, Jan 07 2025

A324234 Number of simple non-isomorphic n-vertex graphs of connectivity 5.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 3, 34, 992, 99419, 21500415, 8004834513

Offset: 1

Jens M. Schmidt, Feb 19 2019

Jens M. Schmidt, Data files in graph6 format

Column k=5 of A259862.

Cf. A052443, A002218.

a(12) added by Brendan McKay, Sep 01 2023

cp's OEIS Frontend

A259862 Triangle read by rows: T(n,k) = number of unlabeled graphs with n nodes and connectivity exactly k (n>=1, 0<=k<=n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A052442 Number of simple unlabeled n-node graphs of connectivity 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A052445 Number of simple unlabeled n-node graphs of connectivity 4.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A327127 Triangle read by rows where T(n,k) is the number of unlabeled simple graphs with n vertices where k is the minimum number of vertices that must be removed (along with any incident edges) to obtain a disconnected or empty graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A327197 Number of set-systems covering n vertices with cut-connectivity 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A327198 Number of labeled simple graphs covering n vertices with vertex-connectivity 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A052444 Number of simple unlabeled n-node graphs of connectivity 3.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A327128 Number of set-systems with n vertices whose edge-set has cut-connectivity 1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A086217 Number of 5-connected graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs