{
  "id": "1202.5721",
  "version": "v1",
  "published": "2012-02-26T03:23:38.000Z",
  "updated": "2012-02-26T03:23:38.000Z",
  "title": "Full Orientability of the Square of a Cycle",
  "authors": [
    "Fengwei Xu",
    "Weifan Wang",
    "Ko-Wei Lih"
  ],
  "comment": "7 pages, accepted by Ars Combinatoria on May 26, 2010",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let D be an acyclic orientation of a simple graph G. An arc of D is called dependent if its reversal creates a directed cycle. Let d(D) denote the number of dependent arcs in D. Define m and M to be the minimum and the maximum number of d(D) over all acyclic orientations D of G. We call G fully orientable if G has an acyclic orientation with exactly k dependent arcs for every k satisfying m <= k <= M. In this paper, we prove that the square of a cycle C_n of length n is fully orientable except n=6.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-02-26T03:23:38.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C99"
    ],
    "keywords": [
      "full orientability",
      "acyclic orientation",
      "dependent arcs",
      "reversal creates",
      "maximum number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 7,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1202.5721X"
    }
  }
}