A326205 Number of n-vertex labeled simple graphs not containing a Hamiltonian path.

1, 1, 1, 4, 30, 391, 9400, 398140, 30500696, 4161339596, 1058339281896, 515295969951016

Offset: 0

Author

Gus Wiseman, Jun 14 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.
• Gus Wiseman, The a(4) = 30 simple graphs not containing a Hamiltonian path.

Crossrefs

The unlabeled case is A283420.

The case for digraphs is A326213 (without loops) or A326216 (with loops).

Simple graphs with a Hamiltonian path are A326206.

Simple graphs without a Hamiltonian cycle are A326207.

Cf. A003216, A006125, A057864.

Programs

Mathematica

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

Formula

A006125(n) = a(n) + A326206(n).

Extensions

a(7)-a(11) added from formula by Falk Hüffner, Jun 21 2019