A321593 Smallest number of vertices supporting a graph with exactly n Hamiltonian paths.

4, 1, 4, 3, 4, 5, 4, 5, 6, 7, 5, 6, 4, 7, 5, 7, 6, 6, 5, 7, 6, 7, 6, 7, 5, 7, 6, 8, 6, 7, 6, 7, 6, 7, 6, 7, 5, 7, 6, 7, 6, 8, 7, 7, 7, 6, 7, 7, 6, 8, 7, 7, 7, 7, 7, 7, 7, 8, 7, 8, 5, 7, 6, 7, 8, 7, 7, 7, 7, 7, 6, 7, 6, 8, 7, 7, 6, 8, 7, 7, 7, 8, 7, 8, 7, 8, 7, 8, 7, 8, 6, 8, 7, 8, 7, 8, 7, 8, 7, 8, 7, 7

Offset

0,1

Comments

The reverse of a path is counted as the same path. a(n) is well-defined as the cycle graph C_n has n paths.

a(n) >= A249905(n) - 1, since the number of Hamiltonian paths in G is the same as the number of Hamiltonian cycles in H, where H is G with a new vertex connected to all vertices in G.

Links

Jeremy Tan, Table of n, a(n) for n = 0..2412

Erich Friedman, Math Magic (September 2012).

Example

a(12) = 4 since K_4 has 12 Hamiltonian paths, and no graph on less than 4 vertices has 12 Hamiltonian paths.

Crossrefs

The corresponding sequence for Hamiltonian cycles is A249905.

Sequence in context: A016686 A060037 A229705 * A173259 A021711 A334487

Adjacent sequences: A321590 A321591 A321592 * A321594 A321595 A321596

Keyword

nonn,hard

Author

Jeremy Tan, Nov 14 2018

Status

approved