cp's OEIS Frontend

A317722 Number of connected graphs with n nodes and no node a member of more than one cycle.

%I A317722 #27 Feb 25 2025 11:37:24
%S A317722 1,1,2,3,8,18,56,165,563,1937,7086,26396,101383,395821,1573317,
%T A317722 6335511,25825861,106344587,441919711,1851114466,7809848543,
%U A317722 33162241547,141636863809,608144007472,2623832050460,11370768445682,49478287669666,216109924932762,947216963083175
%N A317722 Number of connected graphs with n nodes and no node a member of more than one cycle.
%C A317722 The sequence counts connected, loopless, undirected graphs with cycles that do not overlap (cycles have length >= 2), which means any pair of cycles does not have common edges or nodes.
%C A317722 Examples of these graphs are the trees (A000055), the unicyclic graphs (A001429, A002094), or the graphs with cycles without chords.
%C A317722 The concept is both narrower and wider than the concept for Husimi trees, because cycles in Husimi trees may share nodes (but not edges), and because cycles in Husimi trees need to have length >= 3.
%C A317722 There is a mapping/contraction of these graphs to trees: replace each cycle by a single node, attaching all edges that enter a node in the cycle to that node. That tree associated with the graph could be called the skeleton tree.
%C A317722 By reversing that surjection of the graphs to trees, we may generate our graphs with non-overlapping cycles by generating the set of weighted trees (A303841) and replacing the nodes by cycles of lengths that equals their weight.
%H A317722 Andrew Howroyd, <a href="/A317722/b317722.txt">Table of n, a(n) for n = 0..500</a>
%H A317722 R. J. Mathar, <a href="http://arxiv.org/abs/1808.06264">Counting connected graphs without overlapping cycles</a>, arXiv:1808.06264 [math.CO] (2018), series c(n).
%H A317722 R. J. Mathar, <a href="/A317722/a317722_1.pdf">Illustration of the graphs up to n=6</a>
%F A317722 a(n) >= A036250(n).
%o A317722 (PARI)
%o A317722 EulerMTS(p)={my(n=serprec(p,x)-1,vars=variables(p)); exp(sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i))}
%o A317722 raise(p,d) = {my(n=serprec(p,x)-1); substvec(p + O(x^(n\d+1)), [x, y], [x^d,y^d])}
%o A317722 R(n,y)={my(g=x+O(x^2)); for(n=2, n, my(p=x*EulerMTS(g), p2=raise(p,2)); g=p + p*y*(p/(1 - p) + (p + p2)/(1 - p2))/2); g}
%o A317722 G(n,y=1)={my(g=R(n,y), p = x*EulerMTS(g) + O(x*x^n));
%o A317722   my( r=((1 + p)^2/(1 - raise(p,2)) - 1)/2 );
%o A317722   my( c=-sum(d=1, n, eulerphi(d)/d*log(raise(1-p,d))) );
%o A317722   1 + p + (raise(g,2) - g^2 + y*(r + c - 2*p))/2 }
%o A317722 { Vec(G(30)) } \\ _Andrew Howroyd_, Feb 25 2025
%Y A317722 Cf. A036250, A381468 (without 2-cycles).
%K A317722 nonn
%O A317722 0,3
%A A317722 _R. J. Mathar_, Aug 05 2018
%E A317722 a(5) corrected. - _R. J. Mathar_, Aug 12 2018