{
  "id": "2202.09594",
  "version": "v2",
  "published": "2022-02-19T12:47:40.000Z",
  "updated": "2022-10-25T07:52:35.000Z",
  "title": "Independent domination of graphs with bounded maximum degree",
  "authors": [
    "Eun-Kyung Cho",
    "Jinha Kim",
    "Minki Kim",
    "Sang-il Oum"
  ],
  "comment": "14 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "An independent dominating set of a graph, also known as a maximal independent set, is a set $S$ of pairwise non-adjacent vertices such that every vertex not in $S$ is adjacent to some vertex in $S$. We prove that for $\\Delta=4$ or $\\Delta\\ge 6$, every connected $n$-vertex graph of maximum degree at most $\\Delta$ has an independent dominating set of size at most $(1-\\frac{\\Delta}{\\lfloor\\Delta^2/4\\rfloor+\\Delta})(n-1)+1$. In addition, we characterize all connected graphs having the equality and we show that other connected graphs have an independent dominating set of size at most $(1-\\frac{\\Delta}{ \\lfloor\\Delta^2/4\\rfloor+\\Delta})n$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2022-10-25T07:52:35.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bounded maximum degree",
      "independent domination",
      "independent dominating set",
      "maximal independent set",
      "connected graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}