A140638 Number of connected graphs on n labeled nodes that contain at least two cycles.

0, 0, 0, 7, 381, 21748, 1781154, 249849880, 66257728763, 34495508486976, 35641629989151608, 73354595357480683904, 301272202621204113362497, 2471648811029413368450098688, 40527680937730440155535277704046, 1328578958335783199341353852258282496

Offset: 1

Author

Washington Bomfim, May 21 2008

Keywords

• nonn

Comments

These are the connected graphs that are neither trees nor unicyclic.

Also connected non-choosable graphs covering n vertices, where a graph is choosable iff it is possible to choose a different vertex from each edge. The unlabeled version is A140636. The complement is counted by A129271. - Gus Wiseman, Feb 20 2024

References

• J. Riordan, An Introduction to Combinatorial Analysis, Dover, 2002, p. 2.

Links

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

Crossrefs

The unlabeled version is A140636.

Cf. A000272 (trees), A001187 (connected graphs), A057500 (connected unicyclic graphs).

The complement is counted by A129271, unlabeled A005703.

The non-connected complement is A133686, covering A367869.

The non-connected version is A367867, unlabeled A140637.

The non-connected covering version is A367868.

A006125 counts graphs, A000088 unlabeled.

A006129 counts covering graphs, A002494 unlabeled.

A143543 counts simple labeled graphs by number of connected components.

Cf. A001349, A116508, A355740, A367769, A367863, A367901, A367903, A370317.

Programs

Mathematica

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}]],Union@@#==Range[n]&&Length[csm[#]]<=1&&Select[Tuples[#],UnsameQ@@#&]=={}&]],{n,0,5}] (* Gus Wiseman, Feb 19 2024 *)

PARI

seq(n)={my(A=O(x*x^n), t=-lambertw(-x + A)); Vec(serlaplace( log(sum(k=0, n, 2^binomial(k, 2)*x^k/k!, A)) - log(1/(1-t))/2 - t/2 + 3*t^2/4), -n)} \\ Andrew Howroyd, Jan 15 2022

Formula

a(n) = A001187(n) - A129271(n).

a(n) = A001187(n) - A000272(n) - A057500(n).

Extensions

Definition clarified by Andrew Howroyd, Jan 15 2022