A057864 Number of simple traceable graphs on n nodes.

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

Offset

1,3

Comments

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

Links

Table of n, a(n) for n=1..11.

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.

Formula

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

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.

Sequence in context: A227094 A173227 A099556 * A320154 A032273 A143522

Adjacent sequences: A057861 A057862 A057863 * A057865 A057866 A057867

Keyword

nonn,more

Author

Eric W. Weisstein

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

Status

approved