A326219 Number of labeled n-vertex Hamiltonian digraphs (without loops).

0, 1, 1, 15, 1194

Offset

0,4

Comments

A digraph is Hamiltonian if it contains a directed cycle passing through every vertex exactly once.

Links

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

Wikipedia, Hamiltonian path

Formula

A053763(n) = a(n) + A326218(n).

Example

The a(3) = 15 edge-sets:
  {12,23,31}  {12,13,21,32}  {12,13,21,23,31}  {12,13,21,23,31,32}
  {13,21,32}  {12,13,23,31}  {12,13,21,23,32}
              {12,21,23,31}  {12,13,21,31,32}
              {12,23,31,32}  {12,13,23,31,32}
              {13,21,23,32}  {12,21,23,31,32}
              {13,21,31,32}  {13,21,23,31,32}

Mathematica

Table[Length[Select[Subsets[Select[Tuples[Range[n], 2], UnsameQ@@#&]], FindHamiltonianCycle[Graph[Range[n], DirectedEdge@@@#]]!={}&]], {n, 0, 4}] (* Mathematica 8.0+. Warning: Using HamiltonianGraphQ instead of FindHamiltonianCycle returns a(4) = 1200 which is incorrect *)

Crossrefs

The unlabeled case is A326225.

The undirected case is A326208 (without loops) or A326240 (with loops).

The case with loops is A326204.

Digraphs (without loops) not containing a Hamiltonian cycle are A326218.

Digraphs (without loops) containing a Hamiltonian path are A326217.

Cf. A000595, A002416, A003024, A003216, A053763, A246446, A326220, A326226.

Sequence in context: A230669 A027492 A001728 * A211901 A059383 A206394

Adjacent sequences: A326216 A326217 A326218 * A326220 A326221 A326222

Keyword

nonn,more

Author

Gus Wiseman, Jun 15 2019

Status

approved