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

0, 1, 1, 15, 1194

Offset: 0

Author

Gus Wiseman, Jun 15 2019

Keywords

• nonn
• more

Comments

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

Examples

			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}
		

Links

• Wikipedia, Hamiltonian path

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.

Programs

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

Formula

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