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

%I #9 Aug 01 2024 00:09:59

%S 0,0,0,1,15,232,3945,75197,1604974,38122542,1000354710,28790664534,

%T 902783451933,30658102047787,1121532291098765,43985781899812395,

%U 1841621373756094796,82002075703514947236,3869941339069299799884,192976569550677042208068,10139553075163838030949495

%N Number of labeled simple graphs covering n vertices with a unique undirected 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="/A372195/b372195.txt">Table of n, a(n) for n = 0..200</a>

%F Inverse binomial transform of A372193. - _Andrew Howroyd_, Jul 31 2024

%e The a(4) = 15 graphs:

%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}]],Union@@#==Range[n]&&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-x)*(-log(1+w)/2 + w/2 - w^2/4)), -n-1)} \\ _Andrew Howroyd_, Jul 31 2024

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

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

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

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

%Y A000088 counts unlabeled graphs, labeled A006125.

%Y A001858 counts acyclic graphs, unlabeled A005195.

%Y A002807 counts cycles in a complete graph.

%Y A006129 counts labeled graphs, unlabeled A002494.

%Y A322661 counts covering loop-graphs, unlabeled A322700.

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

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

%K nonn

%O 0,5

%A _Gus Wiseman_, Apr 25 2024

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