A006290 -id:A006290 - cp's OEIS frontend

A000088 Number of simple graphs on n unlabeled nodes.

1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005168, 1018997864, 165091172592, 50502031367952, 29054155657235488, 31426485969804308768, 64001015704527557894928, 245935864153532932683719776, 1787577725145611700547878190848, 24637809253125004524383007491432768

Offset: 0

N. J. A. Sloane

Euler transform of the sequence A001349.

Also, number of equivalence classes of sign patterns of totally nonzero symmetric n X n matrices.

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 430.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 519.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 240.
Thomas Boyer-Kassem, Conor Mayo-Wilson, Scientific Collaboration and Collective Knowledge: New Essays, New York, Oxford University Press, 2018, see page 47.
M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 54.
Lupanov, O. B. Asymptotic estimates of the number of graphs with n edges. (Russian) Dokl. Akad. Nauk SSSR 126 1959 498--500. MR0109796 (22 #681).
M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 14-22.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Keith M. Briggs, Table of n, a(n) for n = 0..87 (From link below)
R. Absil and H. Mélot, Digenes: genetic algorithms to discover conjectures about directed and undirected graphs, arXiv preprint arXiv:1304.7993 [cs.DM], 2013.
Natalie Arkus, Vinothan N. Manoharan and Michael P. Brenner. Deriving Finite Sphere Packings, arXiv:1011.5412 [cond-mat.soft], Nov 24, 2010. (See Table 1.)
Leonid Bedratyuk and Anna Bedratyuk, A new formula for the generating function of the numbers of simple graphs, Comptes rendus de l'Académie Bulgare des Sciences, Tome 69, No 3, 2016, p.259-268.
Benjamin A. Blumer, Michael S. Underwood and David L. Feder, Single-qubit unitary gates by graph scattering, arXiv:1111.5032 [quant-ph], 2011.
Keith M. Briggs, Combinatorial Graph Theory [Gives first 140 terms]
Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur and Hadrien Melot, House of Graphs: a database of interesting graphs, arXiv preprint arXiv:1204.3549 [math.CO], 2012.
P. Butler and R. W. Robinson, On the computer calculation of the number of nonseparable graphs, pp. 191 - 208 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp. [Annotated scanned copy]
P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102.
P. J. Cameron, Some sequences of integers, in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
P. J. Cameron and C. R. Johnson, The number of equivalence patterns of symmetric sign patterns, Discr. Math., 306 (2006), 3074-3077.
Gi-Sang Cheon, Jinha Kim, Minki Kim and Sergey Kitaev, On k-11-representable graphs, arXiv:1803.01055 [math.CO], 2018.
CombOS - Combinatorial Object Server, Generate graphs
Karen M. Daehli, Sarah A Obead, Hsuan-Yin Lin, and Eirik Rosnes, Improved Capacity Outer Bound for Private Quadratic Monomial Computation, arXiv:2401.06125 [cs.IR], 2024.
R. L. Davis, The number of structures of finite relations, Proc. Amer. Math. Soc. 4 (1953), 486-495.
J. P. Dolch, Names of Hamiltonian graphs, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 259-271. (Annotated scanned copy of 3 pages)
Peter Dukes, Notes for Math 422: Enumeration and Ramsey Theory, University of Victoria BC Canada (2019). See page 36.
D. S. Dummit, E. P. Dummit and H. Kisilevsky, Characterizations of quadratic, cubic, and quartic residue matrices, arXiv preprint arXiv:1512.06480 [math.NT], 2015.
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
Mareike Fischer, Michelle Galla, Lina Herbst, Yangjing Long, and Kristina Wicke, Non-binary treebased unrooted phylogenetic networks and their relations to binary and rooted ones, arXiv:1810.06853 [q-bio.PE], 2018.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 105.
E. Friedman, Illustration of small graphs
Harald Fripertinger, Graphs
Scott Garrabrant and Igor Pak, Pattern Avoidance is Not P-Recursive, preprint, 2015.
Lee M. Gunderson and Gecia Bravo-Hermsdorff, Introducing Graph Cumulants: What is the Variance of Your Social Network?, arXiv:2002.03959 [math.ST], 2020.
P. Hegarty, On the notion of balance in social network analysis, arXiv preprint arXiv:1212.4303 [cs.SI], 2012.
S. Hougardy, Home Page
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.
Richard Hua and Michael J. Dinneen, Improved QUBO Formulation of the Graph Isomorphism Problem, SN Computer Science (2020) Vol. 1, No. 19.
A. Itzhakov and M. Codish, Breaking Symmetries in Graph Search with Canonizing Sets, arXiv preprint arXiv:1511.08205 [cs.AI], 2015-2016.
Dan-Marian Joiţa and Lorentz Jäntschi, Extending the Characteristic Polynomial for Characterization of C_20 Fullerene Congeners, Mathematics (2017), 5(4), 84.
Vladeta Jovovic, Formulae for the number T(n,k) of n-multigraphs on k nodes
Maksim Karev, The space of framed chord diagrams as a Hopf module, arXiv preprint arXiv:1404.0026 [math.GT], 2014.
J. M. Larson, Cheating Because They Can: Social Networks and Norm Violators, 2014. See Footnote 11.
Steffen Lauritzen, Alessandro Rinaldo and Kayvan Sadeghi, On Exchangeability in Network Models, arXiv:1709.03885 [math.ST], 2017.
O. B. Lupanov, On asymptotic estimates of the number of graphs and networks with n edges, Problems of Cybernetics [in Russian], Moscow 4 (1960): 5-21.
M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 14-22. [Annotated scanned copy]
B. D. McKay, Maple program (used to redirect to here).
B. D. McKay, Maple program [Cached copy, with permission]
B. D. McKay, Simple graphs
A. Milicevic and N. Trinajstic, Combinatorial Enumeration in Chemistry, Chem. Modell., Vol. 4, (2006), pp. 405-469.
Angelo Monti and Blerina Sinaimeri, Effects of graph operations on star pairwise compatibility graphs, arXiv:2410.16023 [cs.DM], 2024. See p. 16.
W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.
M. Petkovsek and T. Pisanski, Counting disconnected structures: chemical trees, fullerenes, I-graphs and others, Croatica Chem. Acta, 78 (2005), 563-567.
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
E. M. Palmer, Letter to N. J. A. Sloane, no date
Marko Riedel, Nonisomorphic graphs.
Marko Riedel, Compact Maple code for cycle index, sequence values and ordinary generating function by the number of edges.
R. W. Robinson, Enumeration of non-separable graphs, J. Combin. Theory 9 (1970), 327-356.
Sage, Common Graphs (Graph Generators)
S. S. Skiena, Generating graphs
N. J. A. Sloane, Illustration of initial terms
Quico Spaen, Christopher Thraves Caro and Mark Velednitsky, The Dimension of Valid Distance Drawings of Signed Graphs, Discrete & Computational Geometry (2019), 1-11.
P. R. Stein, On the number of graphical partitions, pp. 671-684 of Proc. 9th S-E Conf. Combinatorics, Graph Theory, Computing, Congr. Numer. 21 (1978). [Annotated scanned copy]
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Overview of the 17 Parts (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 1
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 2
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 3
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 4
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 5
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 6
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 7
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 8
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 9
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 10
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 11
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 12
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 13
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 14
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 15
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 16
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17
J. M. Tangen and N. J. A. Sloane, Correspondence, 1976-1976
James Turner and William H. Kautz, A survey of progress in graph theory in the Soviet Union SIAM Rev. 12 1970 suppl. iv+68 pp. MR0268074 (42 #2973). See p. 18.
S. Uijlen and B. Westerbaan, A Kochen-Specker system has at least 22 vectors, arXiv preprint arXiv:1412.8544 [cs.DM], 2014.
Mark Velednitsky, New Algorithms for Three Combinatorial Optimization Problems on Graphs, Ph. D. Dissertation, University of California, Berkeley (2020).
Eric Weisstein's World of Mathematics, Simple Graph
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Degree Sequence
E. M. Wright, The number of graphs on many unlabelled nodes, Mathematische Annalen, December 1969, Volume 183, Issue 4, 250-253
E. M. Wright, The number of unlabelled graphs with many nodes and edges Bull. Amer. Math. Soc. Volume 78, Number 6 (1972), 1032-1034.
Chris Ying, Enumerating Unique Computational Graphs via an Iterative Graph Invariant, arXiv:1902.06192 [cs.DM], 2019.
Index entries for "core" sequences

Partial sums of A002494.
Cf. A000666 (graphs with loops), A001349 (connected graphs), A002218, A006290, A003083.
Column k=1 of A063841.
Column k=2 of A309858.
Row sums of A008406.
Cf. also A000055, A000664.
Partial sums are A006897.

# To produce all graphs on 4 nodes, for example:
with(GraphTheory):
L:=[NonIsomorphicGraphs](4,output=graphs,outputform=adjacency): # N. J. A. Sloane, Oct 07 2013
seq(GraphTheory[NonIsomorphicGraphs](n,output=count),n=1..10); # Juergen Will, Jan 02 2018
# alternative Maple program:
b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(ceil((p[j]-1)/2)
      +add(igcd(p[k], p[j]), k=1..j-1), j=1..nops(p)))([l[], 1$n])),
       add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
    end:
a:= n-> b(n$2, []):
seq(a(n), n=0..20);  # Alois P. Heinz, Aug 14 2019

Needs["Combinatorica`"]
Table[NumberOfGraphs[n], {n, 0, 19}] (* Geoffrey Critzer, Mar 12 2011 *)
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 05 2018, after Andrew Howroyd *)
b[n_, i_, l_] := If[n==0 || i==1, 1/n!*2^(Function[p, Sum[Ceiling[(p[[j]]-1 )/2]+Sum[GCD[p[[k]], p[[j]]], {k, 1, j-1}], {j, 1, Length[p]}]][Join[l, Table[1, {n}]]]), Sum[b[n-i*j, i-1, Join[l, Table[i, {j}]]]/j!/i^j, {j, 0, n/i}]];
a[n_] := b[n, n, {}];
a /@ Range[0, 20] (* Jean-François Alcover, Dec 03 2019, after Alois P. Heinz *)

permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, v[i]\2)}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017

from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A000088(n): return int(sum(Fraction(1<>1)*r+(q*r*(r-1)>>1) for q, r in p.items()),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 02 2024

def a(n):
    return len(list(graphs(n)))
# Ralf Stephan, May 30 2014

a(n) = 2^binomial(n, 2)/n!*(1+(n^2-n)/2^(n-1)+8*n!/(n-4)!*(3*n-7)*(3*n-9)/2^(2*n)+O(n^5/2^(5*n/2))) (see Harary, Palmer reference). - Vladeta Jovovic and Benoit Cloitre, Feb 01 2003
a(n) = 2^binomial(n, 2)/n!*[1+2*n$2*2^{-n}+8/3*n$3*(3n-7)*2^{-2n}+64/3*n$4*(4n^2-34n+75)*2^{-3n}+O(n^8*2^{-4*n})] where n$k is the falling factorial: n$k = n(n-1)(n-2)...(n-k+1). - Keith Briggs, Oct 24 2005
From David Pasino (davepasino(AT)yahoo.com), Jan 31 2009: (Start)
a(n) = a(n, 2), where a(n, t) is the number of t-uniform hypergraphs on n unlabeled nodes (cf. A000665 for t = 3 and A051240 for t = 4).
a(n, t) = Sum_{c : 1*c_1+2*c_2+...+n*c_n=n} per(c)*2^f(c), where:
..per(c) = 1/(Product_{i=1..n} c_i!*i^c_i);
..f(c) = (1/ord(c)) * Sum_{r=1..ord(c)} Sum_{x : 1*x_1+2*x_2+...+t*x_t=t} Product_{k=1..t} binomial(y(r, k; c), x_k);
..ord(c) = lcm{i : c_i>0};
..y(r, k; c) = Sum_{s|r : gcd(k, r/s)=1} s*c_(k*s) is the number of k-cycles of the r-th power of a permutation of type c. (End)
a(n) ~ 2^binomial(n,2)/n! [see Flajolet and Sedgewick p. 106, Gross and Yellen, p. 519, etc.]. - N. J. A. Sloane, Nov 11 2013
For asymptotics see also Lupanov 1959, 1960, also Turner and Kautz, p. 18. - N. J. A. Sloane, Apr 08 2014
a(n) = G(1) where G(z) = (1/n!) Sum_g det(I-g z^2)/det(I-g z) and g runs through the natural matrix n X n representation of the pair group A^2_n (for A^2_n see F. Harary and E. M. Palmer, Graphical Enumeration, page 83). - Leonid Bedratyuk, May 02 2015
From Keith Briggs, Jun 24 2016: (Start)
a(n) = 2^binomial(n,2)/n!*(
   1+
   2^(  -n +  1)*n$2+
   2^(-2*n +  3)*n$3*(n-7/3)+
   2^(-3*n +  6)*n$4*(4*n^2/3 - 34*n/3 + 25) +
   2^(-4*n + 10)*n$5*(8*n^3/3 - 142*n^2/3 + 2528*n/9 - 24914/45) +
   2^(-5*n + 15)*n$6*(128*n^4/15 - 2296*n^3/9 + 25604*n^2/9 - 630554*n/45 + 25704) +
   2^(-6*n + 21)*n$7*(2048*n^5/45 - 18416*n^4/9 + 329288*n^3/9 - 131680816*n^2/405 + 193822388*n/135 - 7143499196/2835) + ...),
where n$k is the falling factorial: n$k = n(n-1)(n-2)...(n-k+1), using the method of Wright 1969.
(End)
a(n) = 1/n*Sum_{k=1..n} a(n-k)*A003083(k). - Andrey Zabolotskiy, Aug 11 2020

Harary gives an incorrect value for a(8); compare A007149

A001349 Number of simple connected graphs on n unlabeled nodes.

Original entry on oeis.org

1, 1, 1, 2, 6, 21, 112, 853, 11117, 261080, 11716571, 1006700565, 164059830476, 50335907869219, 29003487462848061, 31397381142761241960, 63969560113225176176277, 245871831682084026519528568, 1787331725248899088890200576580, 24636021429399867655322650759681644

Offset: 0

N. J. A. Sloane

The singleton graph K_1 is considered connected even though it is conventionally taken to have vertex connectivity 0. - Eric W. Weisstein, Jul 21 2020

Inverse Euler transform of A000088 but with a(0) omitted so that Sum_{k>=0} A000088(n) * x^n = Product_{k>0} (1 - x^k)^-a(k). It is debatable if there is a connected graph with 0 nodes and so a(0)=0 or better start from a(1)=1. - Michael Somos, Jun 01 2013. [As Harary once remarked in a famous paper ("Is the null-graph a pointless concept?"), the empty graph has every property, which is why a(0)=1. - N. J. A. Sloane, Apr 08 2014]

			G.f. = 1 + x + x^2 + 2*x^3 + 6*x^4 + 21*x^5 + 112*x^6 + 853*x^7 + ....

P. Butler and R. W. Robinson, On the computer calculation of the number of nonseparable graphs, pp. 191 - 208 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp.
F. Harary and R. C. Read, Is the null-graph a pointless concept?, pp. 37-44 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, page 48, c(x). Also page 242.
Lupanov, O. B. Asymptotic estimates of the number of graphs with n edges. (Russian) Dokl. Akad. Nauk SSSR 126 1959 498--500. MR0109796 (22 #681).
Lupanov, O. B. "On asymptotic estimates of the number of graphs and networks with n edges." Problems of Cybernetics [in Russian], Moscow 4 (1960): 5-21.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1978.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Robin J. Wilson, Introduction to Graph Theory, Academic Press, 1972. (But see A126060!)

N. J. A. Sloane, Table of n, a(n) for n = 0..75 [Computed using Keith Briggs's values for A000088]
Michal Adamaszek, Small flag complexes with torsion, arXiv:1208.3892 [math.CO], 2012.
C. O. Aguilar and B. Gharesifard, Graph Controllability Classes for the Laplacian Leader-Follower Dynamics, 2014. See Table 1.
Jonathan Baker, Kevin N. Vander Meulen, and Adam Van Tuyl, Shedding vertices of vertex decomposable well-covered graphs, Discrete Mathematics (2018) Vol. 341, Issue 12, 3355-3369. Also arXiv:1606.04447 [math.NT], 2016.
Johannes Bausch and Felix Leditzky, Error Thresholds for Arbitrary Pauli Noise, arXiv:1910.00471 [quant-ph], 2019.
Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur and Hadrien Melot, House of Graphs: a database of interesting graphs, arXiv:1204.3549 [math.CO], 2012.
P. Butler and R. W. Robinson, On the computer calculation of the number of nonseparable graphs, pp. 191 - 208 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp. [Annotated scanned copy]
P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102.
P. J. Cameron, Some sequences of integers, in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
CombOS - Combinatorial Object Server, Generate graphs
Matt DeVos, Adam Dyck, Jonathan Jedwab, and Samuel Simon, Which graphs occur as gamma-graphs?, arXiv:1810.01583 [math.CO], 2018.
J. P. Dolch, Names of Hamiltonian graphs, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 259-271. (Annotated scanned copy of 3 pages)
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
E. Friedman, Illustration of small graphs
F. Harary, The number of linear, directed, rooted, and connected graphs, Trans. Am. Math. Soc. 78 (1955) 445-463.
Yoshiaki Horiike and Yuki Kawaguchi, A comprehensive exploration of interaction networks reveals a connection between entanglement and network structure, arXiv:2505.11466 [quant-ph], 2025. See p. 9.
Avraham Itzhakov and Michael Codish, Incremental Symmetry Breaking Constraints for Graph Search Problems, Ben-Gurion University of the Negev (Beer-Sheva, Israel, 2019).
Markus Kirchweger and Stefan Szeider, SAT Modulo Symmetries for Graph Generation and Enumeration, ACM Trans. Comput. Logic (2024). See p. 27.
X. Li, D. S. Stones, H. Wang, H. Deng, X. Liu and G. Wang, NetMODE: Network Motif Detection without Nauty, PLoS ONE 7(12): e50093. - From _N. J. A. Sloane_, Feb 02 2013
Steffen Lauritzen, Alessandro Rinaldo, and Kayvan Sadeghi, On Exchangeability in Network Models, arXiv:1709.03885 [math.ST], 2017.
Richard J. Mathar, Counting Connected Graphs without Overlapping Cycles, arXiv:1808.06264 [math.CO], 2018.
B. D. McKay, Simple Graphs
A. Milicevic and N. Trinajstic, Combinatorial Enumeration in Chemistry, Chem. Modell., Vol. 4, (2006), pp. 405-469.
Marius Möller, Laura Hindersin, and Arne Traulsen, Exploring and mapping the universe of evolutionary graphs, arXiv:1810.12807 [q-bio.PE], 2018.
Marius Möller, Laura Hindersin, and Arne Traulsen, Exploring and mapping the universe of evolutionary graphs identifies structural properties affecting fixation probability and time, Communications Biology 2 (2019), Article number: 137.
L. Naughton and G. Pfeiffer, Integer Sequences Realized by the Subgroup Pattern of the Symmetric Group, J. Int. Seq. 16 (2013) #13.5.8
M. Petkovsek and T. Pisanski, Counting disconnected structures: chemical trees, fullerenes, I-graphs and others, Croatica Chem. Acta, 78 (2005), 563-567.
R. W. Robinson, Enumeration of non-separable graphs, J. Combin. Theory 9 (1970), 327-356.
Gordon Royle, Small graphs
Yoav Spector and Moshe Schwartz, Study of potential Hamiltonians for quantum graphity, arXiv:1808.05632 [cond-mat.stat-mech], 2018.
M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967.
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
D. Stolee, Isomorph-free generation of 2-connected graphs with applications, arXiv:1104.5261 [math.CO], 2011.
Rodrigo Stange Tessinari, Marcia Helena Moreira Paiva, Maxwell E. Monteiro, Marcelo E. V. Segatto, Anilton Garcia, George T. Kanellos, Reza Nejabati, and Dimitra Simeonidou, On the Impact of the Physical Topology on the Optical Network Performance, IEEE British and Irish Conference on Optics and Photonics (BICOP 2018), London.
James Turner and William H. Kautz, A survey of progress in graph theory in the Soviet Union SIAM Rev. 12 1970 suppl. iv+68 pp. MR0268074 (42 #2973). See p. 18. - _N. J. A. Sloane_, Apr 08 2014
Eric Weisstein's World of Mathematics, Connected Graph.
Eric Weisstein's World of Mathematics, k-Connected Graph
Myung-Gon Yoon, Peter Rowlinson, Dragos Cvetkovic, and Zoran Stanic, Controllability of multi-agent dynamical systems with a broadcasting control signal, Asian J. Control 16 (4) (2014) 1066-1072, Table 1.
Index entries for "core" sequences

Cf. A000088, A002218, A006290, A000719, A201922 (Multiset transform).

Row sums of A054924.

# To produce all connected graphs on 4 nodes, for example (from N. J. A. Sloane, Oct 07 2013):
with(GraphTheory):
L:=[NonIsomorphicGraphs](4,output=graphs,outputform=adjacency, restrictto=connected):

<<"Combinatorica`"; max = 19; A000088 = Table[ NumberOfGraphs[n], {n, 0, max}]; f[x_] = 1 - Product[ 1/(1 - x^k)^a[k], {k, 1, max}]; a[0] = a[1] = a[2] = 1; coes = CoefficientList[ Series[ f[x], {x, 0, max}], x]; sol = First[ Solve[ Thread[ Rest[ coes + A000088 ] == 0]]]; Table[ a[n], {n, 0, max}] /. sol (* Jean-François Alcover, Nov 24 2011 *)
terms = 20;
mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
a88[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
Join[{1}, EULERi[Array[a88, terms]]] (* Jean-François Alcover, Jul 28 2018, after Andrew Howroyd *)

from functools import lru_cache
from itertools import combinations
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A001349(n):
    if n == 0: return 1
    @lru_cache(maxsize=None)
    def b(n): return int(sum(Fraction(1<>1)*r+(q*r*(r-1)>>1) for q, r in p.items()),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n)))
    @lru_cache(maxsize=None)
    def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
    return sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n # Chai Wah Wu, Jul 02-03 2024

property=lambda G: G.is_connected()
def a(n):
    return len([1 for G in graphs(n) if property(G)])
# Ralf Stephan, May 30 2014

For asymptotics see Lupanov 1959, 1960, also Turner and Kautz, p. 18. - N. J. A. Sloane, Apr 08 2014

More terms from Ronald C. Read

A002218 Number of unlabeled nonseparable (or 2-connected) graphs (or blocks) with n nodes.

Original entry on oeis.org

0, 1, 1, 3, 10, 56, 468, 7123, 194066, 9743542, 900969091, 153620333545, 48432939150704, 28361824488394169, 30995890806033380784, 63501635429109597504951, 244852079292073376010411280, 1783160594069429925952824734641, 24603887051350945867492816663958981

Offset: 1

N. J. A. Sloane

By definition, a(n) gives the number of graphs with zero cutpoints. - Travis Hoppe, Apr 28 2014
For n > 2, a(n) is also the number of simple biconnected graphs on n nodes. - Eric W. Weisstein, Dec 07 2021
This sequence follows R. W. Robinson's definition of a nonseparable graph which includes K_2 but not the singleton graph K_1. This definition is most suited to graphical enumeration. Other authors sometimes include K_1 as a block or exclude K_2 as not 2-connected. - Andrew Howroyd, Feb 26 2023

P. Butler and R. W. Robinson, On the computer calculation of the number of nonseparable graphs, pp. 191 - 208 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 188.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1978.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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]
P. Butler and R. W. Robinson, On the computer calculation of the number of nonseparable graphs, pp. 191 - 208 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp. [Annotated scanned copy]
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
R. W. Robinson, Computer print-out of first 26 terms [Annotated scanned copy]
R. W. Robinson, Tables
R. W. Robinson, Tables [Local copy, with permission]
R. W. Robinson, Enumeration of non-separable graphs, J. Combin. Theory 9 (1970), 327-356.
R. W. Robinson and T. R. S. Walsh, Inversion of cycle index sum relations for 2- and 3-connected graphs, J. Combin. Theory Ser. B. 57 (1993), 289-308.
R. W. Robinson and T. R. S. Walsh, Inversion of cycle index sum relations for 2- and 3-connected graphs, J. Combin. Theory Ser. B. 57 (1993), 289-308.
Andrés Santos, Density Expansion of the Equation of State, in A Concise Course on the Theory of Classical Liquids, Volume 923 of the series Lecture Notes in Physics, pp 33-96, 2016. DOI:10.1007/978-3-319-29668-5_3. See Reference 40.
Andrew J. Schultz and David A. Kofke, Fifth to eleventh virial coefficients of hard spheres, Phys. Rev. E 90, 023301, 4 August 2014
D. Stolee, Isomorph-free generation of 2-connected graphs with applications, arXiv preprint arXiv:1104.5261 [math.CO], 2011.
Rodrigo Stange Tessinari, Marcia Helena Moreira Paiva, Maxwell E. Monteiro, Marcelo E. V. Segatto, Anilton Garcia, George T. Kanellos, Reza Nejabati, and Dimitra Simeonidou, On the Impact of the Physical Topology on the Optical Network Performance, IEEE British and Irish Conference on Optics and Photonics (BICOP 2018), London.
Eric Weisstein's World of Mathematics, Biconnected Graph
Eric Weisstein's World of Mathematics, k-Connected Graph

Column k=0 of A325111 (for n>1).
Column sums of A339070.
Row sums of A339071.
The labeled version is A013922.
Cf. A000088 (graphs), A001349 (connected graphs), A006289, A006290, A004115 (rooted case), A010355 (by edges), A241767.

\\ See A004115 for graphsSeries and A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(g=graphsSeries(n), gc=sLog(g), gcr=sPoint(gc)); intformal(x*sSolve( sLog( gcr/(x*sv(1)) ), gcr ), sv(1)) + sSolve(subst(gc, sv(1), 0), gcr)}
{ my(N=12); Vec(OgfSeries(cycleIndexSeries(N)), -N) } \\ Andrew Howroyd, Dec 28 2020

More terms from Ronald C. Read. Robinson and Walsh list the first 26 terms.
a(1) changed from 0 to 1 by Eric W. Weisstein, Dec 07 2021
a(1) restored to 0 by Andrew Howroyd, Feb 26 2023

cp's OEIS Frontend

A000088 Number of simple graphs on n unlabeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Sage

Formula

Extensions

A001349 Number of simple connected graphs on n unlabeled nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Sage

Formula

Extensions

A002218 Number of unlabeled nonseparable (or 2-connected) graphs (or blocks) with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

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

A338511 Number of unlabeled 3-connected graphs with n edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A339072 Triangle read by rows: T(n,k) is the number of unlabeled simple 3-connected graphs with n nodes and k edges (n >= 4, ceiling(3*n/2) <= k <= n*(n-1)/2).

Views

Author

Keywords

Examples

Links

Crossrefs

A006289 Number of series-reduced 2-connected graphs with n nodes.

A339072 Triangle read by rows: T(n,k) is the number of unlabeled simple 3-connected graphs with n nodes and k edges (n >= 4, ceiling(3n/2) <= k <= n(n-1)/2).