A372195 Number of labeled simple graphs covering n vertices with a unique undirected cycle of length > 2.

0, 0, 0, 1, 15, 232, 3945, 75197, 1604974, 38122542, 1000354710, 28790664534, 902783451933, 30658102047787, 1121532291098765, 43985781899812395, 1841621373756094796, 82002075703514947236, 3869941339069299799884, 192976569550677042208068, 10139553075163838030949495

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

Inverse binomial transform of A372193. - Andrew Howroyd, Jul 31 2024

Example

The a(4) = 15 graphs:
  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}]], Union@@#==Range[n]&&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-x)*(-log(1+w)/2 + w/2 - w^2/4)), -n-1)} \\ Andrew Howroyd, Jul 31 2024

Crossrefs

For no cycles we have A105784 (for triangles A372168, non-covering A213434), unlabeled A144958 (for triangles A372169).

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

The unlabeled version is A372191, non-covering A236570.

The non-covering version is A372193, column k = 1 of A372176.

A000088 counts unlabeled graphs, labeled A006125.

A001858 counts acyclic graphs, unlabeled A005195.

A002807 counts cycles in a complete graph.

A006129 counts labeled graphs, unlabeled A002494.

A322661 counts covering loop-graphs, unlabeled A322700.

A372167 counts covering graphs by triangles (non-covering A372170), unlabeled A372173 (non-covering A263340).

Cf. A000169, A000272, A053530, A054548, A137916, A137917, A367863, A368597.

Sequence in context: A250418 A231411 A097185 * A178299 A097582 A351527

Adjacent sequences: A372192 A372193 A372194 * A372196 A372197 A372198

Keyword

nonn,changed

Author

Gus Wiseman, Apr 25 2024

Extensions

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

Status

approved