{
  "id": "2003.00729",
  "version": "v1",
  "published": "2020-03-02T09:39:54.000Z",
  "updated": "2020-03-02T09:39:54.000Z",
  "title": "Beyond Hamiltonicity of Prime Difference Graphs",
  "authors": [
    "Hong-Bin Chen",
    "Hung-Lin Fu",
    "Jun-Yi Guo"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-03-02T09:39:54.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "hamiltonicity",
      "result implies robustness",
      "edge-disjoint hamilton cycles",
      "prime difference graph contains considerably",
      "vertex set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}