A381468 -id:A381468 - cp's OEIS frontend

A381467 Triangle read by rows: T(n,k) is the number of simple connected graphs on n unlabeled nodes with k cycles and no node a member of more than one cycle, 0 <= k <= floor(n/3).

1, 1, 1, 1, 1, 2, 2, 3, 5, 6, 13, 1, 11, 33, 4, 23, 89, 21, 47, 240, 85, 2, 106, 657, 345, 16, 235, 1806, 1289, 109, 551, 5026, 4713, 627, 6, 1301, 13999, 16622, 3259, 64, 3159, 39260, 57535, 15576, 598, 7741, 110381, 195212, 69983, 4394, 18, 19320, 311465, 653318, 299354, 28286, 295

Offset: 0

Andrew Howroyd, Feb 24 2025

All such graphs are cactus graphs (with bridges allowed).

			Triangle begins:
     1;
     1;
     1;
     1,     1;
     2,     2;
     3,     5;
     6,    13,     1;
    11,    33,     4;
    23,    89,    21;
    47,   240,    85,     2;
   106,   657,   345,    16;
   235,  1806,  1289,   109;
   551,  5026,  4713,   627,   6;
  1301, 13999, 16622,  3259,  64;
  3159, 39260, 57535, 15576, 598;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1750 (rows 0..100)
R. J. Mathar, Counting connected graphs without overlapping cycles, arXiv:1808.06264 [math.CO] (2018).
Wikipedia, Cactus graph.
Index entries for sequences related to cacti.

Row sums are A381468.
Columns k=0..2 are A000055, A001429, A381470.
Cf. A380631, A380634.

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))}
raise(p,d) = {my(n=serprec(p,x)-1); substvec(p + O(x^(n\d+1)), [x, y], [x^d,y^d])}
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^2/(1 - p) + (1 + p)*p2/(1 - p2))/2); g}
G(n,y=1)={my(g=R(n,y), p = x*EulerMTS(g) + O(x*x^n));
  my( r=((1 + p)^2/(1 - raise(p,2)) - 1)/2 );
  my( c=-sum(d=1, n, eulerphi(d)/d*log(raise(1-p,d))) );
  1 + p + (raise(g,2) - g^2 + y*(r + c - 2*p - p^2 - raise(p,2)))/2 }
T(n)={[Vecrev(p) | p<-Vec(G(n,y))]}
{my(A=T(15)); for(i=1, #A, print(A[i]))}

T(3*n, n) = A380634(n).

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

Original entry on oeis.org

1, 1, 2, 3, 8, 18, 56, 165, 563, 1937, 7086, 26396, 101383, 395821, 1573317, 6335511, 25825861, 106344587, 441919711, 1851114466, 7809848543, 33162241547, 141636863809, 608144007472, 2623832050460, 11370768445682, 49478287669666, 216109924932762, 947216963083175

Offset: 0

R. J. Mathar, Aug 05 2018

nonn

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.
Examples of these graphs are the trees (A000055), the unicyclic graphs (A001429, A002094), or the graphs with cycles without chords.
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.
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.
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.

Andrew Howroyd, Table of n, a(n) for n = 0..500
R. J. Mathar, Counting connected graphs without overlapping cycles, arXiv:1808.06264 [math.CO] (2018), series c(n).
R. J. Mathar, Illustration of the graphs up to n=6

Cf. A036250, A381468 (without 2-cycles).

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))}
raise(p,d) = {my(n=serprec(p,x)-1); substvec(p + O(x^(n\d+1)), [x, y], [x^d,y^d])}
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}
G(n,y=1)={my(g=R(n,y), p = x*EulerMTS(g) + O(x*x^n));
  my( r=((1 + p)^2/(1 - raise(p,2)) - 1)/2 );
  my( c=-sum(d=1, n, eulerphi(d)/d*log(raise(1-p,d))) );
  1 + p + (raise(g,2) - g^2 + y*(r + c - 2*p))/2 }
{ Vec(G(30)) } \\ Andrew Howroyd, Feb 25 2025

a(n) >= A036250(n).

a(5) corrected. - R. J. Mathar, Aug 12 2018

cp's OEIS Frontend

A381467 Triangle read by rows: T(n,k) is the number of simple connected graphs on n unlabeled nodes with k cycles and no node a member of more than one cycle, 0 <= k <= floor(n/3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula