A326226 Number of unlabeled n-vertex Hamiltonian digraphs (with loops).

0, 2, 3, 24, 858

Offset: 0

Author

Gus Wiseman, Jun 14 2019

Keywords

• nonn
• hard
• more

Comments

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

Examples

			Non-isomorphic representatives of the a(2) = 3 digraph edge-sets:
  {12,21}
  {11,12,21}
  {11,12,21,22}
		

Links

• Wikipedia, Hamiltonian path
• Gus Wiseman, Non-isomorphic representatives of the a(3) = 24 Hamiltonian digraphs

Crossrefs

The labeled case is A326204.

The case without loops is A326225.

The undirected case is A003216 (without loops) or A326215 (with loops).

Unlabeled non-Hamiltonian digraphs are A326223.

Unlabeled digraphs with a Hamiltonian path are A326221.

Cf. A000595, A002416, A003087, A057864, A246446, A326208.

Programs

Mathematica

dinorm[m_]:=If[m=={},{},If[Union@@m!=Range[Max@@Flatten[m]],dinorm[m/. Apply[Rule,Table[{(Union@@m)[[i]],i},{i,Length[Union@@m]}],{1}]],First[Sort[dinorm[m,1]]]]];
dinorm[m_,aft_]:=If[Length[Union@@m]<=aft,{m},With[{mx=Table[Count[m,i,{2}],{i,Select[Union@@m,#1>=aft&]}]},Union@@(dinorm[#1,aft+1]&)/@Union[Table[Map[Sort,m/. {par+aft-1->aft,aft->par+aft-1},{0}],{par,First/@Position[mx,Max[mx]]}]]]];
Table[Length[Select[Union[dinorm/@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) = 867 which is incorrect *)