A372175 -id:A372175 - cp's OEIS frontend

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

Gus Wiseman, Apr 25 2024

nonn

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.

			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

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

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.

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

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

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

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

A372194 Number of unlabeled graphs with n vertices and a unique triangle.

Original entry on oeis.org

0, 0, 0, 1, 2, 7, 23, 102, 526, 3624, 32240, 382095, 5986945

Offset: 0

Gus Wiseman, Apr 24 2024

The labeled version is A372172.

			Representatives of the a(3) = 1 through a(6) = 23 graphs:
    12,13,23    12,13,23       12,13,23             12,13,23
                14,23,24,34    12,34,35,45          12,34,35,45
                               14,23,24,34          14,23,24,34
                               12,25,34,35,45       12,25,34,35,45
                               14,25,34,35,45       12,36,45,46,56
                               15,25,34,35,45       13,23,45,46,56
                               12,14,25,34,35,45    14,25,34,35,45
                                                    15,25,34,35,45
                                                    12,14,25,34,35,45
                                                    12,23,36,45,46,56
                                                    13,23,36,45,46,56
                                                    13,25,36,45,46,56
                                                    13,26,36,45,46,56
                                                    14,25,36,45,46,56
                                                    15,26,36,45,46,56
                                                    16,26,36,45,46,56
                                                    12,13,25,36,45,46,56
                                                    12,13,26,36,45,46,56
                                                    13,23,25,36,45,46,56
                                                    14,23,25,36,45,46,56
                                                    16,23,25,36,45,46,56
                                                    13,14,23,25,36,45,46,56
                                                    13,15,23,25,36,45,46,56

Gus Wiseman, The a(3) = 1 through a(6) = 23 graphs with a unique triangle.

For no triangles we have A006785, covering A372169.
Column k = 1 of A263340, covering A372173.
The labeled version is A372172.
The covering case is A372174, labeled A372171.
For all cycles (not just triangles): A236570, A372193, A372191, A372195.
A000088 counts unlabeled graphs, labeled A006125.
A001858 counts acyclic graphs, unlabeled A005195.
A002494 counts unlabeled covering graphs, labeled A006129.
A372176 counts labeled graphs by directed cycles, covering A372175.
Cf. A000055, A137917, A137918, A140637, A144958, A213434, A372168, A372170.

geng $n | countg -T1 # Georg Grasegger, Aug 03 2024

First differences are A372174.

a(11)-a(12) added by Georg Grasegger, Aug 03 2024

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions