|
|
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 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
|
|
|
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.
|
|
KEYWORD
|
nonn,hard
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|