A259862 -id:A259862 - cp's OEIS frontend

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

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

A327236 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of unlabeled simple graphs with n vertices whose edge-set has non-spanning edge-connectivity k.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 1, 4, 5, 10, 8, 5, 1, 1

Offset: 0

Gus Wiseman, Sep 03 2019

The non-spanning edge-connectivity of a graph is the minimum number of edges that must be removed to obtain a disconnected or empty graph, ignoring isolated vertices.

			Triangle begins:
  1
  1
  1  1
  1  1  1  1
  2  2  3  3  1
  4  5 10  8  5  1  1

Gus Wiseman, Unlabeled graphs with 5 vertices, organized by non-spanning edge-connectivity (isolated vertices not shown).

Row sums are A000088.
Column k = 0 is A327235.
The labeled version is A327148.
The covering version is A327201.
Spanning edge-connectivity is A263296.
Vertex-connectivity is A259862.
Cf. A322338, A322396, A326787, A327069, A327077, A327097, A327099, A327102, A327200, A327231.

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]]]]]]]]];
edgeConnSys[sys_]:=If[Length[csm[sys]]!=1,0,Length[sys]-Max@@Length/@Select[Union[Subsets[sys]],Length[csm[#]]!=1&]];
Table[Length[Union[normclut/@Select[Subsets[Subsets[Range[n],{2}]],edgeConnSys[#]==k&]]],{n,0,5},{k,0,Binomial[n,2]}]//.{foe___,0}:>{foe}

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

A327101 BII-numbers of 2-cut-connected set-systems (cut-connectivity >= 2).

Original entry on oeis.org

4, 5, 6, 7, 16, 17, 24, 25, 32, 34, 40, 42, 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

Offset: 1

Gus Wiseman, Aug 22 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.

A set-system is 2-cut-connected if any single vertex can be removed (along with any empty edges) without making the set-system disconnected or empty. Except for cointersecting set-systems (A326853), this is the same as 2-vertex-connectivity.

			The sequence of all 2-cut-connected set-systems together with their BII-numbers begins:
   4: {{1,2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   7: {{1},{2},{1,2}}
  16: {{1,3}}
  17: {{1},{1,3}}
  24: {{3},{1,3}}
  25: {{1},{3},{1,3}}
  32: {{2,3}}
  34: {{2},{2,3}}
  40: {{3},{2,3}}
  42: {{2},{3},{2,3}}
  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}}

Positions of numbers >= 2 in A326786.
2-cut-connected graphs are counted by A013922, if we assume A013922(2) = 0.
2-cut-connected integer partitions are counted by A322387.
BII-numbers for cut-connectivity 2 are A327082.
BII-numbers for cut-connectivity 1 are A327098.
BII-numbers for non-spanning edge-connectivity >= 2 are A327102.
BII-numbers for spanning edge-connectivity >= 2 are A327109.
Covering 2-cut-connected set-systems are counted by A327112.
Covering set-systems with cut-connectivity 2 are counted by A327113.
The labeled cut-connectivity triangle is A327125, with unlabeled version A327127.
Cf. A000120, A002218, A048793, A070939, A259862, A322388, A326031, A326749, A327097, A327108.

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

If (*) is intersection and (-) is complement, we have A327101 * A326704 = A326751 - A058891, i.e., the intersection of A327101 (this sequence) with A326704 (antichains) is the complement of A058891 (singletons) in A326751 (blobs).

A086216 Number of 4-connected unlabeled n-node graphs.

Original entry on oeis.org

0, 0, 0, 0, 1, 4, 25, 384, 14480, 1211735, 184649399, 47952362294

Offset: 1

Eric W. Weisstein, Jul 12 2003

The definition means that the connectivity is 4 or more.

			There are 4 different 4-connected graphs on 6 vertices. - _Dylan Thurston_, Jun 18 2009

Travis Hoppe and Anna Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644, [math.CO], 2014.
Travis Hoppe and Anna Petrone, Integer sequence discovery from small graphs, Discr. Appl. Math. 201 (2016) 172-181.
Eric Weisstein's World of Mathematics, k-Connected Graph

See A052445 for exactly-4-connected graphs.
See A086217 for 5-connected graphs.
See A259862 for further information.

a(n) = A086217(n) + A052445(n). - Andrew Howroyd, Sep 04 2019

Offset corrected by Dylan Thurston, Jun 18 2009
a(10) from the Encyclopedia of Finite Graphs (Travis Hoppe and Anna Petrone), Apr 11 2014
Minor edits by N. J. A. Sloane, Jul 08 2015 at the suggestion of Brendan McKay.
a(12) added by Georg Grasegger, Jan 07 2025

A327112 Number of set-systems covering n vertices with cut-connectivity >= 2, or 2-cut-connected set-systems.

Original entry on oeis.org

0, 0, 4, 72, 29856

Offset: 0

Gus Wiseman, Aug 24 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 empty or duplicate edges) to obtain a disconnected or empty set-system. Except for cointersecting set-systems (A327040), this is the same as vertex-connectivity (A327334, A327051).

			Non-isomorphic representatives of the a(3) = 72 set-systems:
  {{123}}
  {{3}{123}}
  {{23}{123}}
  {{2}{3}{123}}
  {{1}{23}{123}}
  {{3}{23}{123}}
  {{12}{13}{23}}
  {{13}{23}{123}}
  {{1}{2}{3}{123}}
  {{1}{3}{23}{123}}
  {{2}{3}{23}{123}}
  {{3}{12}{13}{23}}
  {{2}{13}{23}{123}}
  {{3}{13}{23}{123}}
  {{12}{13}{23}{123}}
  {{1}{2}{3}{23}{123}}
  {{2}{3}{12}{13}{23}}
  {{1}{2}{13}{23}{123}}
  {{2}{3}{13}{23}{123}}
  {{3}{12}{13}{23}{123}}
  {{1}{2}{3}{12}{13}{23}}
  {{1}{2}{3}{13}{23}{123}}
  {{2}{3}{12}{13}{23}{123}}
  {{1}{2}{3}{12}{13}{23}{123}}

Covering 2-cut-connected graphs are A013922, if we assume A013922(2) = 1.
Covering 1-cut-connected antichains (clutters) are A048143, if we assume A048143(0) = A048143(1) =0.
Covering 2-cut-connected antichains (blobs) are A275307, if we assume A275307(1) = 0.
Covering set-systems with cut-connectivity 2 are A327113.
2-vertex-connected integer partitions are A322387.
BII-numbers of set-systems with cut-connectivity >= 2 are A327101.
The cut-connectivity of the set-system with BII-number n is A326786(n).
Cf. A002218, A003465, A013922, A259862, A323818, A327082, A327126, A327130.

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]]]]]]]]];
vConn[sys_]:=If[Length[csm[sys]]!=1,0,Min@@Length/@Select[Subsets[Union@@sys],Function[del,Length[csm[DeleteCases[DeleteCases[sys,Alternatives@@del,{2}],{}]]]!=1]]];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&vConn[#]>=2&]],{n,0,3}]

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.

A327113 Number of set-systems covering n vertices with cut-connectivity 2.

Original entry on oeis.org

0, 0, 4, 0, 4752

Offset: 0

Gus Wiseman, Aug 24 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 empty or duplicate edges) to obtain a disconnected or empty set-system. Except for cointersecting set-systems (A327040), this is the same as vertex-connectivity (A327334, A327051).

			The a(2) = 4 set-systems:
  {{1,2}}
  {{1},{1,2}}
  {{2},{1,2}}
  {{1},{2},{1,2}}

Covering graphs with cut-connectivity >= 2 are A013922, if we assume A013922(2) = 1.
Covering antichains (blobs) with cut-connectivity >= 2 are A275307, if we assume A275307(1) = 0.
2-vertex-connected integer partitions are A322387.
Connected covering set-systems are A323818.
Covering set-systems with cut-connectivity >= 2 are A327112.
The cut-connectivity of the set-system with BII-number n is A326786(n).
BII-numbers of set-systems with cut-connectivity 2 are A327082.
Cf. A002218, A003465, A048143, A259862, A322389, A327101, A327113, A327126, A327128, A327130.

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]]]]]]]]];
vConn[sys_]:=If[Length[csm[sys]]!=1,0,Min@@Length/@Select[Subsets[Union@@sys],Function[del,Length[csm[DeleteCases[DeleteCases[sys,Alternatives@@del,{2}],{}]]]!=1]]];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&vConn[#]==2&]],{n,0,3}]

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

cp's OEIS Frontend

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A327236 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of unlabeled simple graphs with n vertices whose edge-set has non-spanning edge-connectivity k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A327101 BII-numbers of 2-cut-connected set-systems (cut-connectivity >= 2).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A086216 Number of 4-connected unlabeled n-node graphs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A327112 Number of set-systems covering n vertices with cut-connectivity >= 2, or 2-cut-connected set-systems.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

A327113 Number of set-systems covering n vertices with cut-connectivity 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords