{
  "id": "1901.01959",
  "version": "v1",
  "published": "2019-01-07T18:25:39.000Z",
  "updated": "2019-01-07T18:25:39.000Z",
  "title": "Toughness and prism-hamiltonicity of $P_4$-free graphs",
  "authors": [
    "M. N. Ellingham",
    "Pouria Salehi Nowbandegani",
    "Songling Shan"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "The \\emph{prism} over a graph $G$ is the product $G \\Box K_2$, i.e., the graph obtained by taking two copies of $G$ and adding a perfect matching joining the two copies of each vertex by an edge. The graph $G$ is called \\emph{prism-hamiltonian} if it has a hamiltonian prism. Jung showed that every $1$-tough $P_4$-free graph with at least three vertices is hamiltonian. In this paper, we extend this to observe that for $k \\geq 1$ a $P_4$-free graph has a spanning \\emph{$k$-walk} (closed walk using each vertex at most $k$ times) if and only if it is $\\frac{1}{k}$-tough. As our main result, we show that for the class of $P_4$-free graphs, the three properties of being prism-hamiltonian, having a spanning $2$-walk, and being $\\frac{1}{2}$-tough are all equivalent.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-01-07T18:25:39.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "free graph",
      "prism-hamiltonicity",
      "hamiltonian prism",
      "main result",
      "closed walk"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}