{
  "id": "1907.05966",
  "version": "v1",
  "published": "2019-07-12T21:46:21.000Z",
  "updated": "2019-07-12T21:46:21.000Z",
  "title": "Upper bounds for inverse domination in graphs",
  "authors": [
    "Elliot Krop",
    "Jessica McDonald",
    "Gregory J. Puleo"
  ],
  "comment": "9 pages",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "In any graph $G$, the domination number $\\gamma(G)$ is at most the independence number $\\alpha(G)$. The Inverse Domination Conjecture says that, in any isolate-free $G$, there exists pair of vertex-disjoint dominating sets $D, D'$ with $|D|=\\gamma(G)$ and $|D'| \\leq \\alpha(G)$. Here we prove that this statement is true if the upper bound $\\alpha(G)$ is replaced by $\\frac{3}{2}\\alpha(G) - 1$ (and $G$ is not a clique). We also prove that the conjecture holds whenever $\\gamma(G)\\leq 5$ or $|V(G)|\\leq 16$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-07-12T21:46:21.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69"
    ],
    "keywords": [
      "upper bound",
      "inverse domination conjecture says",
      "domination number",
      "conjecture holds",
      "independence number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}