A057864 Number of simple traceable graphs on n nodes.

1, 1, 2, 5, 18, 91, 734, 10030, 248427, 11482572, 1000231510

Offset: 1

Author

Eric W. Weisstein

Keywords

• nonn
• more

Comments

Number of undirected graphs on n nodes possessing a Hamiltonian path (not circuit).

Links

• F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version f0eaa32.
• Eric Weisstein's World of Mathematics, Traceable Graph
• Wikipedia, Hamiltonian path
• Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.
• Gus Wiseman, Non-isomorphic representatives of the a(5) = 18 unlabeled simple graphs containing a Hamiltonian path.

Crossrefs

Main diagonal of A309524.

The labeled case is A326206.

The directed case is A326221 (with loops).

Unlabeled simple graphs not containing a Hamiltonian path are A283420.

Unlabeled simple graphs containing a Hamiltonian cycle are A003216.

Cf. A000088, A006125, A246446, A283420, A326205, A326217.

Formula

A000088(n) = a(n) + A283420(n). - Gus Wiseman, Jun 17 2019

Extensions

a(8) and a(9) from Eric W. Weisstein, Jun 04 2004

a(10) from Eric W. Weisstein, May 27 2009

a(11) added using tinygraph by Falk Hüffner, Jan 19 2016