{
  "id": "1202.6461",
  "version": "v1",
  "published": "2012-02-29T07:00:02.000Z",
  "updated": "2012-02-29T07:00:02.000Z",
  "title": "The Minimum Number of Dependent Arcs and a Related Parameter of Generalized Mycielski Graphs",
  "authors": [
    "Hsin-Hao Lai",
    "Ko-Wei Lih"
  ],
  "comment": "13 pages, accepted by Utilitas Mathematica on January 14, 2010",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let D be an acyclic orientation of the graph G. An arc of D is dependent if its reversal creates a directed cycle. Let m(G) denote the minimum number of dependent arcs over all acyclic orientations of G. For any k > 0, a generalized Mycielski graph M_k(G) of G is defined. Note that M_1(G) is the usual Mycielskian of G. We generalize results concerning m(M_1(G)) in K. L. Collins, K. Tysdal, J. Graph Theory, 46 (2004), 285-296, to m(M_k(G)). The underlying graph of a Hasse diagram is called a cover graph. Let c(G) denote the the minimum number of edges to be deleted from a graph G to get a cover graph. Analogue results about c(G) are also obtained.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-02-29T07:00:02.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C99"
    ],
    "keywords": [
      "generalized mycielski graph",
      "minimum number",
      "dependent arcs",
      "related parameter",
      "cover graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1202.6461L"
    }
  }
}