A002218 -id:A002218 - cp's OEIS frontend

A010355 Number of unlabeled nonseparable (or 2-connected) graphs (or blocks) with n edges.

1, 0, 1, 1, 2, 4, 7, 16, 42, 111, 331, 1094, 3829, 14380, 57069, 237188, 1027929, 4622588, 21494274, 103077677, 508743475, 2579847563, 13422868110, 71570635306, 390670937143

Offset: 1

N. J. A. Sloane

Original name: Single-edge stars with n edges.

			From _Andrew Howroyd_, Nov 23 2020: (Start)
The a(1) = 1 graph is the single edge (K_2 = P_2).
The a(3) = 1 graph is the triangle (K_3).
The a(4) = 1 graph is the square (C_4).
The a(5) = 2 graphs are the cycle C_5 and a cycle of 4 nodes with one diagonal added.
(End)

George A. Baker Jr. and John M. Kincaid, The continuous-spin Ising model, g0:phi4:d field theory and the renormalization group. J. Statist. Phys. 24 (1981), no. 3, 469-528.
Brendan McKay and Adolfo Piperno, Practical Graph Isomorphism, II, Journal of Symbolic Computation, 60 (2014), pp. 94-112.
Brendan McKay and Adolfo Piperno, nauty and Traces, programs for computing automorphism groups of graphs and digraphs.
R. W. Robinson, Tables of 2-Connected and 3-Connected Graphs by Nodes and Edges, Table IV, pages 4-9.
M. F. Sykes, D. S. McKenzie, and B. R. Heap, Specific heat of a three-dimensional Ising ferromagnet above the Curie temperature. III. The star cluster expansion, J. Phys. A: Math. Nucl. Gen., 7 (1974), 1576.

Row sums of A339070 and A010356.
Column sums of A339071.
Cf. A002218, A010357, A322139, A338511.

a(11)-a(12) from Andrey Zabolotskiy, Oct 03 2017
Name changed by Andrew Howroyd, Nov 23 2020
a(13)-a(18) added using data from Robinson's tables by Andrew Howroyd, Nov 23 2020
a(19)-a(22) from Hugo Pfoertner using program geng from nauty, Dec 04 2020
a(23)-a(24) from Hugo Pfoertner, Dec 07 2020
a(25) from Hugo Pfoertner, Jan 04 2021

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

A003317 Number of unlabeled minimally 2-connected graphs with n nodes (also called "blocks").

Original entry on oeis.org

1, 1, 2, 3, 6, 12, 28, 68, 184, 526, 1602, 5075, 16711, 56428, 195003, 685649, 2447882, 8850157, 32359428, 119492766, 445236635, 1672636369, 6331624545, 24138404479, 92640942148, 357805122286, 1390318899884, 5433781135206

Offset: 3

N. J. A. Sloane

The Pootheri references also contain the edge breakups for each term.

A. M. Hobbs, A catalog of minimal blocks, J. Res. National Bureau Standards, B 77 (1973), 53-60.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Audace A. V. Dossou-Olory, Cut and pendant vertices and the number of connected induced subgraphs of a graph, arXiv:1910.04552 [math.CO], 2019.
A. M. Hobbs, A catalog of minimal blocks, J. Res. National Bureau Standards, B 77 (1973), 53-60. (Annotated scanned copy)
Hu, Guan Zhang; Liu, Guo Qing; Liu, Shi; He, Jian Ping; Enumeration of minimally 2-connected graphs by means of group theory, (Chinese) Acta Math. Appl. Sinica 12 (1989), no. 2, 164-173.
S. K. Pootheri, Counting classes of labeled 2-connected graphs, M.S. Dissertation, University of Georgia, 2000.
S. K. Pootheri, Counting classes of labeled 2-connected graphs, M.S. Thesis, University of Georgia, 2000. [Local copy]
S. K. Pootheri, Characterizing and counting classes of unlabeled 2-connected graphs, Ph. D. Dissertation, University of Georgia, 2000.
S. K. Pootheri, Characterizing and counting classes of unlabeled 2-connected graphs, Ph. D. Dissertation, University of Georgia, 2000. [Local copy]

Cf. A054316, A054317, A002218.

More terms from Sridar K. Pootheri (sridar(AT)math.uga.edu), Feb 25 2000

A021103 Number of two-connected (or biconnected) planar graphs with n nodes.

Original entry on oeis.org

0, 0, 0, 1, 3, 9, 44, 294, 2893, 36496, 545808, 9029737, 159563559, 2952794985, 56589742050

Offset: 0

Brendan McKay

For n < 3, conventions vary: Read & Wilson set a(2) = 0, but Gagarin et al. set a(2) = 1. - Andrey Zabolotskiy, Jun 07 2023

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998. See p. 229.

A. Gagarin, G. Labelle, P. Leroux, and T. Walsh, Structure and enumeration of two-connected graphs with prescribed three-connected components, Adv. in Appl. Math. 43 (2009), no. 1, pp. 46-74. See (116) on p. 69.

Row sums of A049336.
The labeled version is A096331.
Cf. A000944 (3-connected), A002218, A003094, A005470.

a(12)-a(14) from Gilbert Labelle (labelle.gilbert(AT)uqam.ca), Jan 20 2009
Offset 0 from Michel Marcus, Jun 05 2023
a(2) changed back to 0 by Georg Grasegger and Andrey Zabolotskiy, Jun 07 2023

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

A004115 Number of unlabeled rooted nonseparable graphs with n nodes.

Original entry on oeis.org

0, 1, 1, 4, 22, 178, 2278, 46380, 1578060, 92765486, 9676866173, 1821391854302, 625710416245358, 395761853562201960, 464128290507379386872, 1015085639712281997464676, 4160440039279630394986003604, 32088534920274236421098827156776

Offset: 1

N. J. A. Sloane

R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..40 (terms 1..26 from R. W. Robinson)
R. W. Robinson, Rooted non-separable graphs - computer printout

Cf. A002218, A007145, A013922.

\\ See links in A339645 for combinatorial species functions.
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
graphsCycleIndex(n)={my(s=0); forpart(p=n, s+=permcount(p) * 2^edges(p) * sMonomial(p)); s/n!}
graphsSeries(n)={sum(k=0, n, graphsCycleIndex(k)*x^k) + O(x*x^n)}
cycleIndexSeries(n)={my(g=graphsSeries(n), gcr=sPoint(g)/g); x*sSolve( sLog( gcr/(x*sv(1)) ), gcr )}
{ my(N=15); Vec(OgfSeries(cycleIndexSeries(N)), -N) } \\ Andrew Howroyd, Dec 25 2020

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

A339070 Triangle read by rows: T(n,k) is the number of unlabeled nonseparable (or 2-connected) graphs with n edges and k nodes (n >= 1, 2 <= k <= n + 1).

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 2, 1, 0, 0, 0, 0, 3, 3, 1, 0, 0, 0, 0, 2, 9, 4, 1, 0, 0, 0, 0, 1, 14, 20, 6, 1, 0, 0, 0, 0, 1, 12, 50, 40, 7, 1, 0, 0, 0, 0, 0, 8, 82, 161, 70, 9, 1, 0, 0, 0, 0, 0, 5, 94, 429, 433, 121, 11, 1, 0, 0, 0, 0, 0, 2, 81, 780, 1729, 1034, 189, 13, 1, 0

Offset: 1

Andrew Howroyd, Nov 23 2020

			Triangle T(n,k) begins (n edges >= 1, k vertices >= 2):
  1;
  0, 0;
  0, 1, 0;
  0, 0, 1, 0;
  0, 0, 1, 1,  0;
  0, 0, 1, 2,  1,  0;
  0, 0, 0, 3,  3,  1,   0;
  0, 0, 0, 2,  9,  4,   1,   0;
  0, 0, 0, 1, 14, 20,   6,   1,   0;
  0, 0, 0, 1, 12, 50,  40,   7,   1,  0;
  0, 0, 0, 0,  8, 82, 161,  70,   9,  1, 0;
  0, 0, 0, 0,  5, 94, 429, 433, 121, 11, 1, 0;
  ...

Hugo Pfoertner, Table of n, a(n) for n = 1..325 (rows 1..25, first 18 rows extracted from Robinson's tables, rows 19-20 from Andrew Howroyd)
R. W. Robinson, Tables of 2-Connected and 3-Connected Graphs by Nodes and Edges, Table IV, pages 4-9.

Row sums are A010355.
Column sums are A002218.
Cf. A054923, A123534, A253186, A339071 (transpose), A339160.

T(n, n) = 1 for n >= 3.

T(n, n-1) = A253186(n-3) for n >= 3.

First row and column removed by Andrew Howroyd, Dec 05 2020

A241768 Number of simple connected graphs with n nodes and exactly 2 articulation points (cutpoints).

Original entry on oeis.org

0, 0, 0, 1, 3, 17, 101, 890, 11468, 239728

Offset: 1

Travis Hoppe and Anna Petrone, Apr 28 2014

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
Travis Hoppe and Anna Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
Eric Weisstein's World of Mathematics, Articulation Vertex

Column k=2 of A325111.

Cf. other simple connected graph sequences with k articulation points A002218, A241767, A241768, A241769, A241770, A241771.

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

cp's OEIS Frontend

A010355 Number of unlabeled nonseparable (or 2-connected) graphs (or blocks) with n edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A003317 Number of unlabeled minimally 2-connected graphs with n nodes (also called "blocks").

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A021103 Number of two-connected (or biconnected) planar graphs with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A004115 Number of unlabeled rooted nonseparable graphs with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

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

A339070 Triangle read by rows: T(n,k) is the number of unlabeled nonseparable (or 2-connected) graphs with n edges and k nodes (n >= 1, 2 <= k <= n + 1).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A241768 Number of simple connected graphs with n nodes and exactly 2 articulation points (cutpoints).

Views

Author

Keywords

Links