A001429 -id:A001429 - cp's OEIS frontend

A140636 Number of connected graphs on n unlabeled nodes that contain at least two cycles.

0, 0, 0, 2, 13, 93, 809, 11005, 260793, 11715808, 1006698524, 164059824899, 50335907853919, 29003487462805642, 31397381142761123838, 63969560113225175845492, 245871831682084026518599099, 1787331725248899088890197955308, 24636021429399867655322650752269938

Offset: 1

Washington Bomfim, May 20 2008

nonn

Original name: number of unlabeled complex components with n nodes.
We can find in "The Birth of the Giant Component", p. 2, see the first link:
"As each of the random graphs evolved, the story went, never once was there more than a single 'complex' component; i.e. there never were two or more components present simultaneously that were neither trees nor unicyclic."
So a complex component is a connected graph that is neither a tree nor an unicyclic graph.

			a(4) = 2. See the two complex components with 4 nodes in the Sloane illustration.

Andrew Howroyd, Table of n, a(n) for n = 1..50
Svante Janson, Donald E. Knuth, Tomasz Łuczak and Boris Pittel, The Birth of the Giant Component, [DOI], Rand. Struct. Alg. 4 (3) (1993) 233-358
N. J. A. Sloane, Illustration of initial terms of A001349.

The labeled version is A140638.

Cf. A001349, A000055, A001429, A005703.

a(n) = A001349(n) - A005703(n).

a(n) = A001349(n) - A000055(n) - A001429(n).

Name changed by Andrew Howroyd, Jan 16 2022

A368186 Number of n-covers of an unlabeled n-set.

Original entry on oeis.org

1, 1, 2, 9, 87, 1973, 118827, 20576251, 10810818595, 17821875542809, 94589477627232498, 1651805220868992729874, 96651473179540769701281003, 19238331716776641088273777321428, 13192673305726630096303157068241728202, 31503323006770789288222386469635474844616195

Offset: 0

Gus Wiseman, Dec 19 2023

nonn

			Non-isomorphic representatives of the a(1) = 1 through a(3) = 9 set-systems:
  {{1}}  {{1},{2}}    {{1},{2},{3}}
         {{1},{1,2}}  {{1},{2},{1,3}}
                      {{1},{1,2},{1,3}}
                      {{1},{1,2},{2,3}}
                      {{1},{2},{1,2,3}}
                      {{1},{1,2},{1,2,3}}
                      {{1,2},{1,3},{2,3}}
                      {{1},{2,3},{1,2,3}}
                      {{1,2},{1,3},{1,2,3}}

Andrew Howroyd, Table of n, a(n) for n = 0..50

The labeled version is A054780, ranks A367917, non-covering A367916.
The case of graphs is A006649, labeled A367863, cf. A116508, A367862.
The case of connected graphs is A001429, labeled A057500.
Covers with any number of edges are counted by A003465, unlabeled A055621.
A046165 counts minimal covers, ranks A309326.
A058891 counts set-systems, unlabeled A000612, without singletons A016031.
A059201 counts covering T_0 set-systems, unlabeled A319637, ranks A326947.
Cf. A000088, A002494, A006126, A055130, A133686, A140638, A305000, A317795, A326754, A367901, A367902, A367903.

brute[m_]:=Table[Sort[Sort/@(m/.Rule@@@Table[{i, p[[i]]},{i,Length[p]}])], {p,Permutations[Union@@m]}];
Table[Length[Union[First[Sort[brute[#]]]& /@ Select[Subsets[Rest[Subsets[Range[n]]],{n}], Union@@#==Range[n]&]]], {n,0,3}]

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}
K(q, t)={2^sum(j=1, #q, gcd(t, q[j])) - 1}
G(n,m)={if(n==0, 1, my(s=0); forpart(q=n, my(g=sum(t=1, m, K(q,t)*x^t/t, O(x*x^m))); s+=permcount(q)*exp(g - subst(g,x,x^2))); s/n!)}
a(n)=if(n ==0, 1, polcoef(G(n,n) - G(n-1,n), n)) \\ Andrew Howroyd, Jan 03 2024

a(n) = A055130(n, n) for n > 0. - Andrew Howroyd, Jan 03 2024

Terms a(6) and beyond from Andrew Howroyd, Jan 03 2024

A368983 Number of connected graphs with loops (symmetric relations) on n unlabeled vertices with n edges.

Original entry on oeis.org

1, 1, 1, 3, 6, 14, 33, 81, 204, 526, 1376, 3648, 9792, 26485, 72233, 198192, 546846, 1515687, 4218564, 11782427, 33013541, 92759384, 261290682, 737688946, 2086993034, 5915398230, 16795618221, 47763406249, 136028420723, 387928330677, 1107692471888, 3166613486137

Offset: 0

Andrew Howroyd, Jan 11 2024

nonn

The graphs considered here can have loops but not parallel edges.

			Representatives of the a(3) = 3 graphs are:
   {{1,2}, {1,3}, {2,3}},
   {{1}, {1,2}, {1,3}},
   {{1}, {1,2}, {2,3}}.

Andrew Howroyd, Table of n, a(n) for n = 0..500

A diagonal of A322114.
The labeled version is A368951.
Cf. A000081, A001429, A027852, A068051, A283755, A368984 (not necessarily connected).

\\ TreeGf gives gf of A000081.
TreeGf(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
seq(n)={my(t=TreeGf(n)); my(g(e)=subst(t + O(x*x^(n\e)), x, x^e) + O(x*x^n)); Vec(1 + (sum(d=1, n, eulerphi(d)/d*log(1/(1-g(d)))) + ((1+g(1))^2/(1-g(2))-1)/2 - (g(1)^2 + g(2)))/2)}

a(n) = A000081(n) + A001429(n) = A068051(n) - A027852(n) for n > 0.

A002094 Number of unlabeled connected loop-less graphs on n nodes containing exactly one cycle (of length at least 2) and with all nodes of degree <= 4.

Original entry on oeis.org

0, 1, 2, 5, 10, 25, 56, 139, 338, 852, 2145, 5513, 14196, 36962, 96641, 254279, 671640, 1781840, 4742295, 12662282, 33898923, 90981264, 244720490, 659591378, 1781048728, 4817420360, 13050525328, 35405239155, 96180222540, 261603173201, 712364210543

Offset: 1

N. J. A. Sloane

nonn

A pair of parallel edges is permitted and is regarded as a cycle of length 2.
The original definition in A Handbook of Integer Sequences (1973) based on Schiff (1875) was simply "Alcohols". - N. J. A. Sloane, Mar 22 2018
Schiff used an now outdated terminology and did not use the term "alcohols", but in German "zweiwerthige Kohlenwasserstoffe C_{n}H_{2n} ..." and later "... deren je zwei verfuegbare Affinitaeten ... durch Alkoholradikale befriedigt sind.", translated "bivalent hydrocarbons ... whose free valences ... are covered by alcohol radicals". At that time the meaning of "alcohol radical" was different from modern terminology, now meaning an -OH group, but in Schiff's terminology another C_{x}H{y} hydrocarbon group was meant. The organic compounds that are described by the graphs of this sequence in modern chemical terminology are the acyclic alkenes, with exactly one double carbon-to-carbon bond, and the monocyclic cycloalkanes (see Wikipedia links). - Hugo Pfoertner, Mar 29 2018

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).

Vaclav Kotesovec, Table of n, a(n) for n = 1..400
R. J. Mathar, Illustration for graphs up to 6 carbons, 2018
Richard J. Mathar, Counting Connected Graphs without Overlapping Cycles, arXiv:1808.06264 [math.CO], 2018.
Hugo Schiff, Zur Statistik chemischer Verbindungen, Berichte der Deutschen Chemischen Gesellschaft, Vol. 8, pp. 1542-1547, 1875.
Hugo Schiff, Zur Statistik chemischer Verbindungen, Berichte der Deutschen Chemischen Gesellschaft, Vol. 8, pp. 1542-1547, 1875. [Annotated scanned copy]
Wikipedia, Alkene. Those with exactly one double carbon-to-carbon bond are covered by this sequence, the simplest being ethylene C_{2}H_{4}.
Wikipedia, Cycloalkane. The simplest alicyclic compounds, which are the monocyclic saturated hydrocarbons with formula C_{n}H_{2n}, are covered by this sequence, the first example being cyclopropane C_{3}H_{6}.

Cf. A000294, A000598, A000602, A000625, A000642, A001429 (unbound degrees), A068051.

# cycle index of cyclic group C_n
cycC_n := proc(n::integer,a)
    local d ;
    add(numtheory[phi](d)*a[d]^(n/d),d=numtheory[divisors](n)) ;
    %/n ;
end proc:
# cycle index of dihedral group
cyD_n := proc(n::integer,a)
    cycC_n(n,a)/2 ;
    if type(n,'odd') then
        %+ a[1]*a[2]^((n-1)/2)/2 ;
    else
        %+ ( a[1]^2*a[2]^((n-2)/2) +a[2]^(n/2) )/4 ;
    end if;
end proc:
a000642 := [
    1, 1, 2, 3, 7, 14, 32, 72, 171, 405, 989, 2426, 6045, 15167, 38422, 97925,
    251275, 648061, 1679869, 4372872, 11428365, 29972078, 78859809, 208094977,
    550603722, 1460457242, 3882682803, 10344102122, 27612603765, 73844151259,
    197818389539, 530775701520, 1426284383289] ;
g := [add(a000642[i]*x^i,i=1..nops(a000642)) ];
for i from 2 to nops(a000642) do
    g := [op(g), subs(x=x^i,g[1]) ] ;
end do:
Nmax := nops(a000642) :
G := 0 ;
for c from 2 to Nmax do
    f := cyD_n(c,g) ;
    G := G+ taylor(f,x=0,Nmax) ;
end do:
taylor(G,x=0,Nmax) ;
gfun[seriestolist](%) ; # R. J. Mathar, Mar 17 2018

terms = 31;
cycC[n_, a_] := Sum[EulerPhi[d] a[[d]]^(n/d), {d, Divisors[n]}]/n;
cyD[n_, a_] := Module[{cc}, cc = (1/2)cycC[n, a]; If[OddQ[n], (1/2)a[[1]]* a[[2]]^((n-1)/2)+cc, (1/4)(a[[1]]^2 a[[2]]^((n-2)/2) + a[[2]]^(n/2)) + cc]];
B[] = 0; Do[B[x] = Normal[(1/6) x (2 B[x^3] + 3 B[x^2] B[x] + B[x]^3) + O[x]^terms+1], terms];
A[x_] = (1/2) x (B[x^2] + B[x]^2) + O[x]^(terms+2);
a000642 = Rest[CoefficientList[A[x], x]];
g = {Sum[x^i a000642[[i]], {i, 1, terms+1}]};
For[i = 2, i <= Length[a000642], i++, g = Flatten[Append[g, g[[1]] /. x -> x^i]]];
For[G = 0; c = 2, c < terms+1, c++, f = cyD[c, g]; G = Series[f, {x, 0, terms+1}] + G];
Most[Rest[CoefficientList[G, x]]] (* Jean-François Alcover, Mar 26 2020, after R. J. Mathar *)

Let A(x) denote the generating function for A000598 (Number of rooted ternary trees with n nodes), i.e., A(x) = 1+(1/6)*x*(A(x)^3+3*A(x)*A(x^2)+2*A(x^3)), and set B(x)=(A(x)^2+A(x^2))/2. With D_k(x) being the cycle polynomial of the regular k-gon for k>=2, the final generating function is then given by Sum_{k>=2} x^k*D_k(B(x)), which can be evaluated very quickly. - Sascha Kurz, Mar 18 2018

Better definition from R. J. Mathar; terms beyond 852 from R. J. Mathar and Sean A. Irvine, Mar 17 2018

A000368 Number of connected graphs with one cycle of length 4.

Original entry on oeis.org

1, 1, 4, 9, 28, 71, 202, 542, 1507, 4114, 11381, 31349, 86845, 240567, 668553, 1860361, 5188767, 14495502, 40572216, 113743293, 319405695, 898288484, 2530058013, 7135848125, 20152898513, 56986883801

Offset: 4

N. J. A. Sloane

nonn

F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973, page 69.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.
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).

Vaclav Kotesovec, Table of n, a(n) for n = 4..2000 (terms 4..43 from Sean A. Irvine, 44..200 from Washington Bomfim)
Washington Bomfim, Illustration of initial terms

Column k=4 of A217781.
Cf. A000081, A000226, A001429, A005703.
Second diagonal of A058879.

Needs["Combinatorica`"]; nn = 30; s[n_, k_] := s[n, k] = a[n + 1 - k] + If[n < 2 k, 0, s[n - k, k]]; a[1] = 1; a[n_] := a[n] = Sum[a[i] s[n - 1, i] i, {i, 1, n - 1}]/(n - 1); rt = Table[a[i], {i, 1, nn}]; Take[CoefficientList[CycleIndex[DihedralGroup[4], s] /. Table[s[j] -> Table[Sum[rt[[i]] x^(k*i), {i, 1, nn}], {k, 1, nn}][[j]], {j, 1, nn}], x], {5, nn}]  (* Geoffrey Critzer, Oct 12 2012, after code given by Robert A. Russell in A000081 *)
A000081 = Rest[Cases[ Import["https://oeis.org/A000081/b000081.txt", "Table"], {, }][[All, 2]]]; max = 30; g81 = Sum[A000081[[k]]*x^k, {k, 1, max}]; g81x2 = Sum[A000081[[k]]*x^(2 k), {k, 1, max}]; g81x4 = Sum[A000081[[k]]*x^(4 k), {k, 1, max}]; Drop[CoefficientList[ Series[(2*g81x4 + 3*g81x2^2 + 2*g81^2*g81x2 + g81^4)/8, {x, 0, max}], x], 4] (* Vaclav Kotesovec, Dec 25 2020 *)

g(Q)={my(V=Vec(Q),D=Set(V),d=#D); if(d==4,return(3*f[D[1]]*f[D[2]]*f[D[3]]*f[D[4]]));
if(d==1, return((f[D[1]]^4+2*f[D[1]]^3+3*f[D[1]]^2+2*f[D[1]])/8));
my(k=1, m = #select(x->x == D[k],V), t); while(m==1, k++; m = #select(x->x == D[k], V)); t = D[1]; D[1] = D[k]; D[k] = t;
if(d == 3, return( f[D[1]] * f[D[2]] * f[D[3]] * (3 * f[D[1]] + 1)/2 ) );
if(m==3, return(f[D[1]]^2 * f[D[2]] * (f[D[1]] + 1)/2));
((3*f[D[2]]^2 + f[D[2]])*f[D[1]]^2 + (f[D[2]]^2 + 3*f[D[2]])*f[D[1]])/4 };
seq(max_n) = { my(s, a = vector(max_n), U); f = vector(max_n); f[1] = 1;
for(j=1, max_n - 1, if(j%100==0,print(j)); f[j+1] = 1/j * sum(k=1, j, sumdiv(k,d, d * f[d]) * f[j-k+1]));
for(n=4, max_n, s=0; forpart(Q = n, if( (Q[4] > Q[3]) && (Q[3]-1 > Q[2]),
      U = U / (f[Q[4] + 1] * f[Q[3] - 1]) * f[Q[4]] * f[Q[3]],  U = g(Q)); s += U,
[1,n],[4,4]); a[n] = s; if(n % 100 == 0, print(n": " s))); a[4..max_n] };
\\ Washington Bomfim, Jul 19 2012 and Dec 22 2020

From Washington Bomfim, Jul 19 2012 and Dec 22 2020: (Start)
a(n) = Sum_{P}( g(Q) ), where P is the set of the partitions Q of n with 4 parts, Q with distinct parts D[1]..D[d], D[1] the part of maximum multiplicity m in Q, f(n) = A000081(n), and g(Q) given by,
       | 3 * f(D[1]) * f(D[2]) * f(D[3]) * f(D[4]),              if d = 4,
       | (f(D[1])^4 + 2*f(D[1])^3 + 3*f(D[1])^2 + 2*f(D[1]))/8,  if d = 1,
g(Q) = | f(D[1]) * f(D[2]) * f(D[3]) * (3 * f(D[1]) + 1)/2,      if d = 3,
       | ((3*f(D[2])^2+f(D[2]))*f(D[1])^2+(f(D[2])^2+3*f(D[2]))*f(D[1]))/4,
       |                                                   if d=2, and m=2,
       | f(D[1])^2 * f(D[2]) * (f(D[1]) + 1)/2,            if d=2, and m=3.
(End)
G.f.: (2*t(x^4) + 3*t(x^2)^2 + 2*t(x)^2*t(x^2) + t(x)^4)/8 where t(x) is the g.f. of A000081. - Andrew Howroyd, Dec 03 2020
a(n) ~ (A187770 + A339986) * A051491^n / (2 * n^(3/2)). - Vaclav Kotesovec, Dec 25 2020

More terms from Vladeta Jovovic, Apr 20 2000
Definition improved by Franklin T. Adams-Watters, May 16 2006
More terms from Sean A. Irvine, Nov 14 2010

A370318 Number of labeled simple graphs with n vertices and the same number of edges as covered vertices, such that the edge set is connected.

Original entry on oeis.org

0, 0, 0, 1, 19, 307, 5237, 99137, 2098946, 49504458, 1291570014, 37002273654, 1156078150969, 39147186978685, 1428799530304243, 55933568895261791, 2338378885159906196, 103995520598384132516, 4903038902046860966220, 244294315694676224001852, 12827355456239840407125363

Offset: 0

Gus Wiseman, Feb 18 2024

nonn

The case of an empty edge set is excluded.

Andrew Howroyd, Table of n, a(n) for n = 0..100

The covering case is A057500, which is also the covering case of A370317.
This is the connected case of A367862, covering A367863.
A001187 counts connected graphs, A001349 unlabeled.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A062734 counts connected graphs by edge count.
A133686 = graphs satisfy strict AoC, connected A129271, covering A367869.
A143543 counts simple labeled graphs by number of connected components.
A367867 = graphs contradict strict AoC, connected A140638, covering A367868.
Cf. A001429, A006649, A061540, A116508, A323818, A367916, A368951, A369197.

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}], Length[Intersection@@s[[#]]]>0&]},If[c=={},s, csm[Sort[Append[Delete[s,List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]],Length[#]==Length[Union@@#] && Length[csm[#]]==1&]],{n,0,5}]

\\ Compare A370317; use A057500 for efficiency.
a(n)=n!*polcoef(polcoef(exp(x*y + O(x*x^n))*(-x+log(sum(k=0, n, (1 + y + O(y*y^n))^binomial(k, 2)*x^k/k!, O(x*x^n)))), n), n) \\ Andrew Howroyd, Feb 19 2024

Binomial transform of A057500 (if the null graph is not connected).

a(n) = n!*[x^n][y^n] exp(x*y)*(-x + log(Sum_{k>=0} (1 + y)^binomial(k, 2)*x^k/k!)). - Andrew Howroyd, Feb 19 2024

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).

Original entry on oeis.org

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).

A001435 Number of connected graphs with n nodes and n+1 edges.

Original entry on oeis.org

0, 0, 0, 1, 5, 19, 67, 236, 797, 2678, 8833, 28908, 93569, 300748, 959374, 3042808, 9597679, 30134509, 94218306, 293509092, 911325798, 2821327949, 8711297753, 26833501800, 82476837698, 253007383067, 774737986836

Offset: 1

N. J. A. Sloane

nonn

This enumerates the connected graphs of complexity 2, in the terminology of Spencer, p. 720. We define the complexity of a component [of the random graph] with V vertices and E edges as E-V+1. Trees [A000055] and unicyclic graphs [A001429] have complexity 0 and 1, respectively, and are called simple. A diagonal of A076263. - Jonathan Vos Post, Jun 26 2010

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).

Sean A. Irvine, Table of n, a(n) for n = 1..40
Joel Spencer, The Giant Component: The Golden Anniversary, Notices of the AMS, Vol. 57, No. 6, June/July 2010, 720-724
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.

Cf. A000055, A001429, A076263.

Description corrected by and more terms from Ronald C. Read, Aug 02 1996

a(27) corrected by Sean A. Irvine, Jul 23 2012

A058879 Triangle read by rows: T(n,k) = number of connected graphs with one cycle of length m = n - k + 1 and n nodes (n >= 3 and 1 <= k <= n - 2).

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 1, 4, 7, 1, 1, 4, 9, 18, 1, 1, 5, 10, 28, 44, 1, 1, 5, 13, 32, 71, 117, 1, 1, 6, 14, 45, 89, 202, 299, 1, 1, 6, 17, 52, 130, 264, 542, 793, 1, 1, 7, 19, 69, 163, 413, 751, 1507, 2095, 1, 1, 7, 22, 79, 224, 544, 1221, 2179, 4114, 5607

Offset: 3

N. J. A. Sloane, Jan 07 2001

Diagonals give A000226, A000368. Row sums give A001429.
From Washington Bomfim, Jul 06 2008: (Start)
T(n,3) = 2 + floor(m/2). When k = 3, n = m + 2, so we have unicyclic graphs of order m+2 with a cycle of length m. Only two nodes of those graphs belong to the rooted trees attached to the cycle, so the orders of those trees can be only 1, 2, or 3.
We can have only one tree of order 3 in those graphs. So the two different rooted trees of order 3 correspond to two unicycles.
We can have two trees of order 2 in those graphs. Those trees can be rooted at two points r_1, r_2 of the cycle in h = floor(m/2) ways. They can be neighbors, i.e., we have an edge of the cycle (r_1, r_2). They can be 2, 3, ..., h edges apart, but they cannot be h+1 edges away from each other. This is true because we obtain an isomorphic graph if r_1 and r_2 are h+1 (or more) edges apart, since there are also n - (h+1) edges between r_1 and r_2 and n-h-1 <= h. Note that there is only one rooted tree of order two.
The five unicyclic graphs of order 9 with a cycle of length 7 are depicted in the picture corresponding to the link.
T(n,4) = 4 + 2floor(m/2) + nearest integer to m^2/12.
We have unicyclic graphs of order m+3 with a cycle of length m. Only three nodes of those graphs belong to the rooted trees attached to the cycle, so the orders of those trees can be only 1, 2, 3, or 4. The set of unicycles can be divided in graphs with trees of orders
4,1,1,...,1
3,2,1,...,1
2,2,2,1,...,1.
Since there are 4 rooted trees of order 4, the orders 4,1,1,...,1 correspond to 4 unicycles.
The orders 3,2,1,...,1 correspond to 2floor(m/2) unicycles. For each one of the two rooted trees of order 3, we see above that there are floor(m/2) possibilities to choose a root for the tree of order 2.
The orders 2,2,2,1,...,1 correspond to i unicycles, i = nearest integer to m^2/12. This follows from the number of necklaces with n+3 beads 3 of which are red, that is equal to the nearest integer to (n+3)^2/12. See A001399. In our case we have necklaces with m beads. The 3 red beads are the roots of the trees of order 2. (End)

			Triangle begins:
  1;
  1,  1;
  1,  1,  3;
  1,  1,  4,  7;
  1,  1,  4,  9, 18;

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 69, (3.4.1).
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150, Table 9.

Washington Bomfim, The five unicyclic graphs of order 9 with a cycle of length 7: T(9,3)=5.

Cf. A000081, A217781.

Needs["NumericalDifferentialEquationAnalysis`"];
t[n_, k_] := Block[{x}, Coefficient[CycleIndexPolynomial[DihedralGroup[n + 1 - k], Table[ButcherTreeCount[n].x^(p Range[n]), {p, n + 1 - k}]], x, n]];
Table[t[n, k], {n, 13}, {k, 1, n - 2}] // Flatten
(* requires Mathematica 9+; Andrey Zabolotskiy, May 12 2017 *)

T(n, k) = [x^n] Z(D_{n+1-k}; t(x)) where t(x) is the g.f. of A000081 and Z(D_m) is the cycle index of the dihedral group of order m. - Sean A. Irvine, Sep 03 2022

More terms from Washington Bomfim, May 12 2008
More terms from Washington Bomfim, Jul 06 2008
Rows n = 11 to 13 added, name and offset corrected by Andrey Zabolotskiy, May 12 2017

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

A140636 Number of connected graphs on n unlabeled nodes that contain at least two cycles.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A368186 Number of n-covers of an unlabeled n-set.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A368983 Number of connected graphs with loops (symmetric relations) on n unlabeled vertices with n edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A002094 Number of unlabeled connected loop-less graphs on n nodes containing exactly one cycle (of length at least 2) and with all nodes of degree <= 4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A000368 Number of connected graphs with one cycle of length 4.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A370318 Number of labeled simple graphs with n vertices and the same number of edges as covered vertices, such that the edge set is connected.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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