Beyond Hamiltonicity of Prime Difference Graphs
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 Gn, which will be called the prime difference graph of order n, with vertex set {1,2,⋯,n} and edge set {uv:∣u−v∣ is a prime number}. A recent result, conjectured by Sun and later proved by Chen, asserts that Gn is Hamiltonian for n≥5. This paper extends their result in three directions. First, we prove that for any two integers a and b with 1≤a<b≤n, there is a Hamilton path in Gn 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 Gn 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≥7, the prime difference graph Gn contains any 2-factor of the complete graph of order n as a subgraph. Finally, we find that Gn may contain more edge-disjoint Hamilton cycles. In particular, these Hamilton cycles are generated by two prime differences.