{
  "id": "1505.03459",
  "version": "v1",
  "published": "2015-05-13T17:08:55.000Z",
  "updated": "2015-05-13T17:08:55.000Z",
  "title": "On powers of interval graphs and their orders",
  "authors": [
    "Florent Foucaud",
    "Reza Naserasr",
    "Aline Parreau",
    "Petru Valicov"
  ],
  "comment": "4 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "It was proved by Raychaudhuri in 1987 that if a graph power $G^{k-1}$ is an interval graph, then so is the next power $G^k$. This result was extended to $m$-trapezoid graphs by Flotow in 1995. We extend the statement for interval graphs by showing that any interval representation of $G^{k-1}$ can be extended to an interval representation of $G^k$ that induces the same left endpoint and right endpoint orders. The same holds for unit interval graphs. We also show that a similar fact does not hold for trapezoid graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-05-13T17:08:55.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "trapezoid graphs",
      "interval representation",
      "unit interval graphs",
      "right endpoint orders",
      "graph power"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 4,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150503459F"
    }
  }
}