

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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,1


COMMENTS

The reverse of a path is counted as the same path. a(n) is welldefined 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 A267633 A021711
Adjacent sequences: A321590 A321591 A321592 * A321594 A321595 A321596


KEYWORD

nonn,hard


AUTHOR

Jeremy Tan, Nov 14 2018


STATUS

approved



