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

0, 0, 1, 4, 34, 633, 23368, 1699012, 237934760, 64558137140, 34126032806936, 35513501049012952

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

• F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 9766535.
• 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) = 34 simple graphs containing a Hamiltonian path

Crossrefs

The unlabeled case is A057864.

The directed case is A326214 (with loops) or A326217 (without loops).

Simple graphs without a Hamiltonian path are A326205.

Simple graphs with a Hamiltonian cycle are A326208.

Cf. A003216, A006125, A057864, A283420.

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) + A326205(n).

Extensions

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