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

Author

Gus Wiseman, Apr 25 2024

Keywords

• nonn

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.

Examples

			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
		

Links

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

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.

Programs

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}]

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

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

Extensions

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