{
  "id": "2112.11720",
  "version": "v2",
  "published": "2021-12-22T08:08:10.000Z",
  "updated": "2021-12-29T12:51:12.000Z",
  "title": "Tight bound for independent domination of cubic graphs without $4$-cycles",
  "authors": [
    "Eun-Kyung Cho",
    "Ilkyoo Choi",
    "Hyemin Kwon",
    "Boram Park"
  ],
  "comment": "16 pages, 4 figures",
  "journal": "J. Graph Theory 104.2 (2023) 372-386",
  "doi": "10.1002/jgt.22968",
  "categories": [
    "math.CO"
  ],
  "abstract": "Given a graph $G$, a dominating set of $G$ is a set $S$ of vertices such that each vertex not in $S$ has a neighbor in $S$. The domination number of $G$, denoted $\\gamma(G)$, is the minimum size of a dominating set of $G$. The independent domination number of $G$, denoted $i(G)$, is the minimum size of a dominating set of $G$ that is also independent. Recently, Abrishami and Henning proved that if $G$ is a cubic graph with girth at least $6$, then $i(G) \\le \\frac{4}{11}|V(G)|$. We show a result that not only improves upon the upper bound of the aforementioned result, but also applies to a larger class of graphs, and is also tight. Namely, we prove that if $G$ is a cubic graph without $4$-cycles, then $i(G) \\le \\frac{5}{14}|V(G)|$, which is tight. Our result also implies that every cubic graph $G$ without $4$-cycles satisfies $\\frac{i(G)}{\\gamma(G)} \\le \\frac{5}{4}$, which partially answers a question by O and West in the affirmative.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2021-12-29T12:51:12.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69"
    ],
    "keywords": [
      "cubic graph",
      "tight bound",
      "dominating set",
      "independent domination number",
      "minimum size"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}