A326226 - OEIS

A326226

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

0, 2, 3, 24, 858

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

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

LINKS

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

Wikipedia, Hamiltonian path

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

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.

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

Sequence in context: A374858 A372737 A193338 * A291262 A307922 A048674

Adjacent sequences: A326223 A326224 A326225 * A326227 A326228 A326229

KEYWORD

nonn,hard,more

AUTHOR

Gus Wiseman, Jun 14 2019

STATUS

approved