{
  "id": "2107.02796",
  "version": "v1",
  "published": "2021-07-06T03:16:57.000Z",
  "updated": "2021-07-06T03:16:57.000Z",
  "title": "Double domination in maximal outerplanar graphs",
  "authors": [
    "Wei Zhuang"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "In a graph $G$, a vertex dominates itself and its neighbors. A subset $S\\subseteq V(G)$ is said to be a double dominating set of $G$ if $S$ dominates every vertex of $G$ at least twice. The double domination number $\\gamma_{\\times 2}(G)$ is the minimum cardinality of a double dominating set of $G$. We show that if $G$ is a maximal outerplanar graph on $n\\geq 3$ vertices, then $\\gamma_{\\times 2}(G)\\leq \\lfloor \\frac{2n}{3}\\rfloor$. Further, if $n\\geq 4$, then $\\gamma_{\\times 2}(G)\\leq \\min \\{\\lfloor \\frac{n+t}{2}\\rfloor, n-t\\}$, where $t$ is the number of vertices of degree $2$ in $G$. These bounds are shown to be tight. In addition, we also study the case that $G$ is a striped maximal outerplanar graph.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-07-06T03:16:57.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "double dominating set",
      "striped maximal outerplanar graph",
      "double domination number",
      "vertex dominates",
      "minimum cardinality"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}