{
  "id": "1403.2796",
  "version": "v1",
  "published": "2014-03-12T02:19:31.000Z",
  "updated": "2014-03-12T02:19:31.000Z",
  "title": "The Algorithmic Complexity of Bondage and Reinforcement Problems in bipartite graphs",
  "authors": [
    "Fu-Tao Hu",
    "Moo Young Sohn"
  ],
  "comment": "13 pages, 4 figures. arXiv admin note: substantial text overlap with arXiv:1109.1657; and text overlap with arXiv:1204.4010 by other authors",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G=(V,E)$ be a graph. A subset $D\\subseteq V$ is a dominating set if every vertex not in $D$ is adjacent to a vertex in $D$. The domination number of $G$, denoted by $\\gamma(G)$, is the smallest cardinality of a dominating set of $G$. The bondage number of a nonempty graph $G$ is the smallest number of edges whose removal from $G$ results in a graph with domination number larger than $\\gamma(G)$. The reinforcement number of $G$ is the smallest number of edges whose addition to $G$ results in a graph with smaller domination number than $\\gamma(G)$. In 2012, Hu and Xu proved that the decision problems for the bondage, the total bondage, the reinforcement and the total reinforcement numbers are all NP-hard in general graphs. In this paper, we improve these results to bipartite graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-03-12T02:19:31.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "05C85",
      "F.2.2"
    ],
    "keywords": [
      "bipartite graphs",
      "reinforcement problems",
      "algorithmic complexity",
      "smallest number",
      "domination number larger"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1403.2796H"
    }
  }
}