{
  "id": "2007.15504",
  "version": "v1",
  "published": "2020-07-30T14:53:02.000Z",
  "updated": "2020-07-30T14:53:02.000Z",
  "title": "Domination in digraphs and their products",
  "authors": [
    "Boštjan Brešar",
    "Kirsti Kuenzel",
    "Douglas F. Rall"
  ],
  "comment": "22 pages and 5 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "A dominating (respectively, total dominating) set $S$ of a digraph $D$ is a set of vertices in $D$ such that the union of the closed (respectively, open) out-neighborhoods of vertices in $S$ equals the vertex set of $D$. The minimum size of a dominating (respectively, total dominating) set of $D$ is the domination (respectively, total domination) number of $D$, denoted $\\gamma(D)$ (respectively,$\\gamma_t(D)$). The maximum number of pairwise disjoint closed (respectively,open) in-neighborhoods of $D$ is denoted by $\\rho(D)$ (respectively,$\\rho^{\\rm o}(D)$). We prove that in digraphs whose underlying graphs have girth at least $7$, the closed (respectively,open) in-neighborhoods enjoy the Helly property, and use these two results to prove that in any ditree $T$ (that is, a digraph whose underlying graph is a tree), $\\gamma_t(T)=\\rho^{\\rm o}(T)$ and $\\gamma(T)=\\rho(T)$. By using the former equality we then prove that $\\gamma_t(G\\times T)=\\gamma_t(G)\\gamma_t(T)$, where $G$ is any digraph and $T$ is any ditree, each without a source vertex, and $G\\times T$ is their direct product. From the equality $\\gamma(T)=\\rho(T)$ we derive the bound $\\gamma(G\\mathbin{\\Box} T)\\ge\\gamma(G)\\gamma(T)$, where $G$ is an arbitrary digraph, $T$ an arbitrary ditree and $G\\mathbin{\\Box} T$ is their Cartesian product. In general digraphs this Vizing-type bound fails, yet we prove that for any digraphs $G$ and $H$, where $\\gamma(G)\\ge\\gamma(H)$, we have $\\gamma(G \\mathbin{\\Box} H) \\ge \\frac{1}{2}\\gamma(G)(\\gamma(H) + 1)$. This inequality is sharp as demonstrated by an infinite family of examples. Ditrees $T$ and digraphs $H$ enjoying $\\gamma(T\\mathbin{\\Box} H)=\\gamma(T)\\gamma(H)$ are also investigated.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-07-30T14:53:02.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C20",
      "05C69",
      "05C76"
    ],
    "keywords": [
      "domination",
      "vizing-type bound fails",
      "source vertex",
      "maximum number",
      "in-neighborhoods enjoy"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}