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

Author

Jeremy Tan, Nov 14 2018

Keywords

• nonn
• hard

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.

Examples

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

Links

• Jeremy Tan, Table of n, a(n) for n = 0..2412
• Erich Friedman, Math Magic (September 2012).

Crossrefs

The corresponding sequence for Hamiltonian cycles is A249905.