{
  "id": "1012.1231",
  "version": "v2",
  "published": "2010-12-06T16:37:30.000Z",
  "updated": "2011-02-22T02:38:23.000Z",
  "title": "A sufficient condition for the existence of an anti-directed 2-factor in a directed graph",
  "authors": [
    "Ajit A. Diwan",
    "Josh B. Frye",
    "Michael J. Plantholt",
    "Shailesh K. Tipnis"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let D be a directed graph with vertex set V and order n. An anti-directed hamiltonian cycle H in D is a hamiltonian cycle in the graph underlying D such that no pair of consecutive arcs in H form a directed path in D. An anti-directed 2-factor in D is a vertex-disjoint collection of anti-directed cycles in D that span V. It was proved in [3] that if the indegree and the outdegree of each vertex of D is greater than (9/16)n then D contains an anti-directed hamilton cycle. In this paper we prove that given a directed graph D, the problem of determining whether D has an anti-directed 2-factor is NP-complete, and we use a proof technique similar to the one used in [3] to prove that if the indegree and the outdegree of each vertex of D is greater than (24/46)n then D contains an anti-directed 2-factor.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2011-02-22T02:38:23.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C20",
      "05C45"
    ],
    "keywords": [
      "directed graph",
      "sufficient condition",
      "proof technique similar",
      "vertex-disjoint collection",
      "anti-directed hamiltonian cycle"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1012.1231D"
    }
  }
}