A004108 Number of n-node unlabeled connected graphs without endpoints.

1, 1, 0, 1, 3, 11, 61, 507, 7442, 197772, 9808209, 902884343, 153723152913, 48443147912137, 28363697921914475, 30996525982586676021, 63502034385272108655525, 244852545421597419740767106, 1783161611489937453151313949442, 24603891216883233547700609793901996

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

Comments

Also number of n-node unlabeled connected mating graphs, cf. A006024 and A092430 (conjectured by Vladeta Jovovic, proved by G. Kilibarda). - Vladeta Jovovic, Oct 07 2004

References

• F. Harary and E. Palmer, Graphical Enumeration, (1973), formula (8.7.11).
• Goran Kilibarda, "Enumeration of unlabeled mating graphs", Belgrade, 2004, to be published.
• R. W. Robinson, personal communication.
• R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1977.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 1..26 from R. W. Robinson)
• David Cook II, Nested colourings of graphs, arXiv preprint arXiv:1306.0140 [math.CO], 2013.
• Gabe Cunningham and Igor Minevich, Graph Products of Groups, arXiv:2502.05648 [math.GR], 2025. See p. 5.
• Hemanshu Kaul and Jeffrey A. Mudrock, Counting List Colorings of Unlabeled Graphs, arXiv:2409.06063 [math.CO], 2024. See p. 6.
• Goran Kilibarda, Enumeration of Unlabeled Mating Graphs, Graphs and Combinatorics, Volume 23, Number 2 / April, 2007, pp. 183-199.
• R. W. Robinson, Connected graphs without endpoints - computer printout.
• Eric Weisstein's World of Mathematics, Connected Graph.

Crossrefs

Cf. A059166 (n-node connected labeled graphs without endpoints), A059167 (n-node labeled graphs without endpoints), A004110 (Euler Transform, n-node unlabeled graphs without endpoints).

Cf. A006024, A092430 (n-node labeled connected mating graphs).

See also A261919.

Cf. A342556, A342557.

Counts include those for distance-critical graphs, A349402.

Programs

Mathematica

terms = 19;
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]];
b[n_] := Sum[permcount[p]*2^edges[p]*Coefficient[Product[1 - x^p[[i]], {i, 1, Length[p]}], x, n - k]/k!, {k, 1, n}, {p, IntegerPartitions[k]}];
A004110 = Table[b[n], {n, 1, terms-1}];
Join[{1}, EULERi[A004110]] (* Jean-François Alcover, Jan 21 2019, after Andrew Howroyd *)

Formula

Inverse Euler transform of A004110. - Andrew Howroyd, Sep 09 2018

Extensions

a(0)=1 prepended by Andrew Howroyd, Sep 09 2018