login
A321593
Smallest number of vertices supporting a graph with exactly n Hamiltonian paths.
1
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
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
KEYWORD
nonn,hard
AUTHOR
Jeremy Tan, Nov 14 2018
STATUS
approved