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

%I #15 Aug 01 2024 00:10:15

%S 0,0,0,1,19,317,5582,108244,2331108,55636986,1463717784,42182876763,

%T 1323539651164,44955519539963,1644461582317560,64481138409909506,

%U 2698923588248208224,120133276796015812548,5667351458582453925696,282496750694780020437765,14837506263979393796687088

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

%C 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.

%H Andrew Howroyd, <a href="/A372193/b372193.txt">Table of n, a(n) for n = 0..200</a>

%F 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

%e The a(4) = 19 graphs:

%e 12,13,23

%e 12,14,24

%e 13,14,34

%e 23,24,34

%e 12,13,14,23

%e 12,13,14,24

%e 12,13,14,34

%e 12,13,23,24

%e 12,13,23,34

%e 12,13,24,34

%e 12,14,23,24

%e 12,14,23,34

%e 12,14,24,34

%e 12,23,24,34

%e 13,14,23,24

%e 13,14,23,34

%e 13,14,24,34

%e 13,23,24,34

%e 14,23,24,34

%t 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[#]&];

%t Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Length[cyc[#]]==2&]],{n,0,5}]

%o (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

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

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

%Y The unlabeled version is A236570, non-covering A372191.

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

%Y A000088 counts unlabeled graphs, labeled A006125.

%Y A002807 counts cycles in a complete graph.

%Y A006129 counts labeled graphs, unlabeled A002494.

%Y A372167 counts graphs by triangles, non-covering A372170.

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

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

%K nonn

%O 0,5

%A _Gus Wiseman_, Apr 25 2024

%E a(7) onwards from _Andrew Howroyd_, Jul 31 2024