  A graph is Hamiltonian if it contains a cycle which visits every vertex of
the graph exactly once. In this paper, we consider the problem of Hamiltonicity
of a graph $G_n$, which will be called the prime difference graph of order $n$,
with vertex set $\{1,2,\cdots, n\}$ and edge set $\{uv: |u-v|$ is a prime
number$\}$. A recent result, conjectured by Sun and later proved by Chen,
asserts that $G_n$ is Hamiltonian for $n\geq 5$. This paper extends their
result in three directions. First, we prove that for any two integers $a$ and
$b$ with $1\leq a<b\leq n$, there is a Hamilton path in $G_n$ from $a$ to $b$
except some cases of small $n$. This result implies robustness of the
Hamiltonicity property of the prime difference graph in a sense that for any
edge $e$ in $G_n$ there exists a Hamilton cycle containing $e$. Second, we show
that the prime difference graph contains considerably more about the cycle
structure than Hamiltonicity; precisely, for any integer $n\geq 7$, the prime
difference graph $G_n$ contains any 2-factor of the complete graph of order $n$
as a subgraph. Finally, we find that $G_n$ may contain more edge-disjoint
Hamilton cycles. In particular, these Hamilton cycles are generated by two
prime differences.
