The minimum number of Hamilton cycles in a hamiltonian threshold graph of a prescribed order

Abstract

We prove that the minimum number of Hamilton cycles in a hamiltonian threshold graph of order $n$ is $2^{\lfloor (n-3)/2\rfloor }$ and this minimum number is attained uniquely by the graph with degree sequence $n-1,n-1,n-2,\dots ,\lceil n/2\rceil ,\lceil n/2\rceil ,\dots ,3,2$ of $n-2$ distinct degrees. This graph is also the unique graph of minimum size among all hamiltonian threshold graphs of order $n.$

8 pages