A052442 -id:A052442 - 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.

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.

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

A327336 Number of labeled simple graphs with vertex-connectivity 1.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Sep 02 2019

nonn

Same as A327114 except a(2) = 1.

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.

			The a(2) = 1 through a(4) = 28 edge-sets:
  {12}  {12,13}  {12,13,14}
        {12,23}  {12,13,24}
        {13,23}  {12,13,34}
                 {12,14,23}
                 {12,14,34}
                 {12,23,24}
                 {12,23,34}
                 {12,24,34}
                 {13,14,23}
                 {13,14,24}
                 {13,23,24}
                 {13,23,34}
                 {13,24,34}
                 {14,23,24}
                 {14,23,34}
                 {14,24,34}
                 {12,13,14,23}
                 {12,13,14,24}
                 {12,13,14,34}
                 {12,13,23,24}
                 {12,13,23,34}
                 {12,14,23,24}
                 {12,14,24,34}
                 {12,23,24,34}
                 {13,14,23,34}
                 {13,14,24,34}
                 {13,23,24,34}
                 {14,23,24,34}

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

Column k = 1 of A327334.
The unlabeled version is A052442.
Connected non-separable graphs are A013922.
Set-systems with vertex-connectivity 1 are A327128.
Labeled simple graphs with cut-connectivity 1 are A327114.
Cf. A006129, A054592, A322389, A322390, A326786, A327070, A327098, A327100, A327125, A327126.

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

Terms a(6) and beyond from Andrew Howroyd, Sep 11 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.

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A327336 Number of labeled simple graphs with vertex-connectivity 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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.