login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A326219 Number of labeled n-vertex Hamiltonian digraphs (without loops). 7
0, 1, 1, 15, 1194 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

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

FORMULA

A053763(n) = a(n) + A326218(n).

EXAMPLE

The a(3) = 15 edge-sets:

  {12,23,31}  {12,13,21,32}  {12,13,21,23,31}  {12,13,21,23,31,32}

  {13,21,32}  {12,13,23,31}  {12,13,21,23,32}

              {12,21,23,31}  {12,13,21,31,32}

              {12,23,31,32}  {12,13,23,31,32}

              {13,21,23,32}  {12,21,23,31,32}

              {13,21,31,32}  {13,21,23,31,32}

MATHEMATICA

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

CROSSREFS

The unlabeled case is A326225.

The undirected case is A326208 (without loops) or A326240 (with loops).

The case with loops is A326204.

Digraphs (without loops) not containing a Hamiltonian cycle are A326218.

Digraphs (without loops) containing a Hamiltonian path are A326217.

Cf. A000595, A002416, A003024, A003216, A053763, A246446, A326220, A326226.

Sequence in context: A230669 A027492 A001728 * A211901 A059383 A206394

Adjacent sequences:  A326216 A326217 A326218 * A326220 A326221 A326222

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Jun 15 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 April 8 08:54 EDT 2020. Contains 333313 sequences. (Running on oeis4.)