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!)
A326214 Number of labeled n-vertex digraphs (with loops) containing a (directed) Hamiltonian path. 6
0, 0, 12, 384, 53184 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

A path is Hamiltonian if it passes through every vertex exactly once.

LINKS

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

Wikipedia, Hamiltonian path

Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs.

FORMULA

A002416(n) = a(n) + A326213(n).

EXAMPLE

The a(2) = 12 edge-sets:

  {12}

  {21}

  {11,12}

  {11,21}

  {12,21}

  {12,22}

  {21,22}

  {11,12,21}

  {11,12,22}

  {11,21,22}

  {12,21,22}

  {11,12,21,22}

MATHEMATICA

Table[Length[Select[Subsets[Tuples[Range[n], 2]], FindHamiltonianPath[Graph[Range[n], DirectedEdge@@@#]]!={}&]], {n, 4}] (* Mathematica 10.2+ *)

CROSSREFS

The unlabeled case is A326221.

The undirected case is A326206.

The case without loops is A326217.

Digraphs not containing a Hamiltonian path are A326213.

Digraphs containing a Hamiltonian cycle are A326204.

Cf. A000595, A002416, A003024, A003216, A057864, A326224, A326225, A326226.

Sequence in context: A251590 A196459 A193132 * A187513 A138914 A326220

Adjacent sequences:  A326211 A326212 A326213 * A326215 A326216 A326217

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 September 23 04:19 EDT 2021. Contains 347609 sequences. (Running on oeis4.)