login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A326226 Number of unlabeled n-vertex Hamiltonian digraphs (with loops). 10
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: A013312 A013318 A193338 * A291262 A307922 A048674

Adjacent sequences:  A326223 A326224 A326225 * A326227 A326228 A326229

KEYWORD

nonn,hard,more

AUTHOR

Gus Wiseman, Jun 14 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 21 04:22 EST 2019. Contains 329350 sequences. (Running on oeis4.)