cp's OEIS Frontend

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

%I A004108 M2910 #77 Feb 17 2025 12:20:40
%S A004108 1,1,0,1,3,11,61,507,7442,197772,9808209,902884343,153723152913,
%T A004108 48443147912137,28363697921914475,30996525982586676021,
%U A004108 63502034385272108655525,244852545421597419740767106,1783161611489937453151313949442,24603891216883233547700609793901996
%N A004108 Number of n-node unlabeled connected graphs without endpoints.
%C A004108 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
%D A004108 F. Harary and E. Palmer, Graphical Enumeration, (1973), formula (8.7.11).
%D A004108 Goran Kilibarda, "Enumeration of unlabeled mating graphs", Belgrade, 2004, to be published.
%D A004108 R. W. Robinson, personal communication.
%D A004108 R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1977.
%D A004108 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A004108 Andrew Howroyd, <a href="/A004108/b004108.txt">Table of n, a(n) for n = 0..50</a> (terms 1..26 from R. W. Robinson)
%H A004108 David Cook II, <a href="http://arxiv.org/abs/1306.0140">Nested colourings of graphs</a>, arXiv preprint arXiv:1306.0140 [math.CO], 2013.
%H A004108 Gabe Cunningham and Igor Minevich, <a href="https://arxiv.org/abs/2502.05648">Graph Products of Groups</a>, arXiv:2502.05648 [math.GR], 2025. See p. 5.
%H A004108 Hemanshu Kaul and Jeffrey A. Mudrock, <a href="https://arxiv.org/abs/2409.06063">Counting List Colorings of Unlabeled Graphs</a>, arXiv:2409.06063 [math.CO], 2024. See p. 6.
%H A004108 Goran Kilibarda, <a href="http://dx.doi.org/10.1007/s00373-007-0692-5">Enumeration of Unlabeled Mating Graphs</a>, Graphs and Combinatorics, Volume 23, Number 2 / April, 2007, pp. 183-199.
%H A004108 R. W. Robinson, <a href="/A004108/a004108.pdf">Connected graphs without endpoints - computer printout</a>.
%H A004108 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/ConnectedGraph.html">Connected Graph</a>.
%F A004108 Inverse Euler transform of A004110. - _Andrew Howroyd_, Sep 09 2018
%t A004108 terms = 19;
%t A004108 mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
%t A004108 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]];
%t A004108 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];
%t A004108 edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
%t A004108 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]}];
%t A004108 A004110 = Table[b[n], {n, 1, terms-1}];
%t A004108 Join[{1}, EULERi[A004110]] (* _Jean-François Alcover_, Jan 21 2019, after _Andrew Howroyd_ *)
%Y A004108 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).
%Y A004108 Cf. A006024, A092430 (n-node labeled connected mating graphs).
%Y A004108 See also A261919.
%Y A004108 Cf. A342556, A342557.
%Y A004108 Counts include those for distance-critical graphs, A349402.
%K A004108 nonn
%O A004108 0,5
%A A004108 _N. J. A. Sloane_
%E A004108 a(0)=1 prepended by _Andrew Howroyd_, Sep 09 2018