{
  "id": "1205.4322",
  "version": "v1",
  "published": "2012-05-19T12:22:27.000Z",
  "updated": "2012-05-19T12:22:27.000Z",
  "title": "A generalization of Opsut's lower bounds for the competition number of a graph",
  "authors": [
    "Yoshio Sano"
  ],
  "comment": "6 pages. arXiv admin note: text overlap with arXiv:0905.1763",
  "journal": "Graphs and Combinatorics 29 (2013) 1543-1547",
  "doi": "10.1007/s00373-012-1188-5",
  "categories": [
    "math.CO"
  ],
  "abstract": "The notion of a competition graph was introduced by J. E. Cohen in 1968. The competition graph C(D) of a digraph $D$ is a (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if there exists a vertex v in D such that (x,v) and (y,v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. In 1978, F. S. Roberts defined the competition number k(G) of a graph G as the minimum number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and it has been one of the important research problems in the study of competition graphs to characterize a graph by its competition number. In 1982, R. J. Opsut gave two lower bounds for the competition number of a graph. In this paper, we give a generalization of these two lower bounds for the competition number of a graph.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-05-19T12:22:27.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C20",
      "05C69"
    ],
    "keywords": [
      "competition number",
      "opsuts lower bounds",
      "competition graph",
      "generalization",
      "important research problems"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1205.4322S"
    }
  }
}