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

%I #12 Aug 13 2020 14:02:28

%S 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,

%T 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,

%U 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

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

%C 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.

%C 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.

%H Jeremy Tan, <a href="/A321593/b321593.txt">Table of n, a(n) for n = 0..2412</a>

%H Erich Friedman, <a href="https://erich-friedman.github.io/mathmagic/0912.html">Math Magic</a> (September 2012).

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

%Y The corresponding sequence for Hamiltonian cycles is A249905.

%K nonn,hard

%O 0,1

%A _Jeremy Tan_, Nov 14 2018