login
A326226
Number of unlabeled n-vertex Hamiltonian digraphs (with loops).
10
0, 2, 3, 24, 858
OFFSET
0,2
COMMENTS
A digraph is Hamiltonian if it contains a directed cycle passing through every vertex exactly once.
EXAMPLE
Non-isomorphic representatives of the a(2) = 3 digraph edge-sets:
{12,21}
{11,12,21}
{11,12,21,22}
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 *)
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.
Sequence in context: A374858 A372737 A193338 * A291262 A307922 A048674
KEYWORD
nonn,hard,more
AUTHOR
Gus Wiseman, Jun 14 2019
STATUS
approved