A326213 Number of labeled n-vertex digraphs (with loops) not containing a (directed) Hamiltonian path.

1, 2, 4, 128, 12352, 3826272, 3775441536

Offset: 0

Author

Gus Wiseman, Jun 15 2019

Keywords

• nonn
• more

Comments

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

Links

• Wikipedia, Hamiltonian path
• Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.

Crossrefs

The unlabeled case is A326224.

The case without loops is A326216.

Digraphs containing a Hamiltonian path are A326214.

Digraphs not containing a Hamiltonian cycle are A326220.

Cf. A000595, A002416, A003024, A003216, A057864, A283420, A326204, A326206, A326221.

Programs

Mathematica

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

Formula

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

Extensions

a(5)-a(6) from Bert Dobbelaere, Jun 11 2024