A372193 Number of labeled simple graphs on n vertices with a unique cycle of length > 2.

0, 0, 0, 1, 19, 317, 5582, 108244, 2331108, 55636986, 1463717784, 42182876763, 1323539651164, 44955519539963, 1644461582317560, 64481138409909506, 2698923588248208224, 120133276796015812548, 5667351458582453925696, 282496750694780020437765, 14837506263979393796687088

Offset

0,5

Comments

An undirected cycle in a graph is a sequence of distinct vertices, up to rotation and reversal, such that there are edges between all consecutive elements, including the last and the first.

Links

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

Formula

E.g.f.: B(x)*C(x) where B(x) is the e.g.f. of A057500 and C(x) is the e.g.f. of A001858. - Andrew Howroyd, Jul 31 2024

Example

The a(4) = 19 graphs:
  12,13,23
  12,14,24
  13,14,34
  23,24,34
  12,13,14,23
  12,13,14,24
  12,13,14,34
  12,13,23,24
  12,13,23,34
  12,13,24,34
  12,14,23,24
  12,14,23,34
  12,14,24,34
  12,23,24,34
  13,14,23,24
  13,14,23,34
  13,14,24,34
  13,23,24,34
  14,23,24,34

Mathematica

cyc[y_]:=Select[Join@@Table[Select[Join@@Permutations /@ Subsets[Union@@y, {k}], And @@ Table[MemberQ[Sort/@y, Sort[{#[[i]], #[[If[i==k, 1, i+1]]]}]], {i, k}]&], {k, 3, Length[y]}], Min@@#==First[#]&];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Length[cyc[#]]==2&]], {n, 0, 5}]

Prog

(PARI) seq(n)={my(w=lambertw(-x+O(x*x^n))); Vec(serlaplace(exp(-w-w^2/2)*(-log(1+w)/2 + w/2 - w^2/4)), -n-1)} \\ Andrew Howroyd, Jul 31 2024

Crossrefs

For no cycles we have A001858 (covering A105784), unlabeled A005195 (covering A144958).

Counting triangles instead of cycles gives A372172 (non-covering A372171), unlabeled A372194 (non-covering A372174).

The unlabeled version is A236570, non-covering A372191.

The covering case is A372195, column k = 1 of A372175.

A000088 counts unlabeled graphs, labeled A006125.

A002807 counts cycles in a complete graph.

A006129 counts labeled graphs, unlabeled A002494.

A372167 counts graphs by triangles, non-covering A372170.

A372173 counts unlabeled graphs by triangles, non-covering A263340.

Cf. A000272, A054548, A057500, A121251, A137916, A213434, A322661, A372169, A372176.

Sequence in context: A138943 A111420 A166965 * A137352 A027541 A143699

Adjacent sequences: A372190 A372191 A372192 * A372194 A372195 A372196

Keyword

nonn

Author

Gus Wiseman, Apr 25 2024

Extensions

a(7) onwards from Andrew Howroyd, Jul 31 2024

Status

approved