0,4

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

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

Wikipedia, Hamiltonian path

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

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}

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 *)

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

nonn,more

Gus Wiseman, Jun 15 2019

approved