A372172 Number of labeled simple graphs on n vertices with exactly one triangle.

0, 0, 0, 1, 16, 290, 6980, 235270, 11298056, 777154308, 76560083040

Offset

0,5

Comments

The unlabeled version is A372194.

Links

Table of n, a(n) for n=0..10.

Formula

Binomial transform of A372171.

Example

The a(4) = 16 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,14,23,24
  12,14,24,34
  12,23,24,34
  13,14,23,34
  13,14,24,34
  13,23,24,34
  14,23,24,34

Mathematica

cys[y_]:=Select[Subsets[Union@@y, {3}], MemberQ[y, {#[[1]], #[[2]]}] && MemberQ[y, {#[[1]], #[[3]]}] && MemberQ[y, {#[[2]], #[[3]]}]&];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Length[cys[#]]==1&]], {n, 0, 5}]

Crossrefs

For no triangles we have A213434, covering A372168 (unlabeled A372169).

Column k = 1 of A372170, unlabeled A263340.

The covering case is A372171, unlabeled A372174.

For all cycles (not just triangles) we have A372193, covering A372195.

The unlabeled version is A372194.

A001858 counts acyclic graphs, unlabeled A005195.

A006125 counts simple graphs, unlabeled A000088.

A006129 counts covering graphs, unlabeled A002494

A054548 counts labeled covering graphs by edges, unlabeled A370167.

A372167 counts covering graphs by triangles, unlabeled A372173.

Cf. A000272, A105784, A121251, A137916, A236570, A372176.

Sequence in context: A140770 A099279 A202878 * A183886 A230341 A278304

Adjacent sequences: A372169 A372170 A372171 * A372173 A372174 A372175

Keyword

nonn,more,changed

Author

Gus Wiseman, Apr 24 2024

Extensions

a(8)-a(10) from Andrew Howroyd, Aug 01 2024

Status

approved