login
Number of Hamiltonian labeled n-vertex digraphs (with loops).
12

%I #13 Jul 23 2019 04:25:16

%S 0,2,4,120,19104

%N Number of Hamiltonian labeled n-vertex digraphs (with loops).

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

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Hamiltonian_path">Hamiltonian path</a>

%e The a(2) = 4 digraph edge-sets:

%e {12,21}

%e {11,12,21}

%e {12,21,22}

%e {11,12,21,22}

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

%Y The unlabeled case is A326226.

%Y The case without loops is A326219.

%Y The undirected case (without loops) is A326208.

%Y Non-Hamiltonian digraphs are A326220.

%Y Digraphs containing a Hamiltonian path are A326214.

%Y Cf. A000595, A002416, A003024, A003216, A057864.

%K nonn,more

%O 0,2

%A _Gus Wiseman_, Jun 14 2019