{
  "id": "2308.15603",
  "version": "v1",
  "published": "2023-08-29T19:50:17.000Z",
  "updated": "2023-08-29T19:50:17.000Z",
  "title": "$k$-tuple domination on Kneser graphs",
  "authors": [
    "María Gracia Cornet",
    "Pablo Torres"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "In this paper, we continue the study of different types of dominating sets in Kneser graphs. We focus on $k$-tuple dominating sets, $2$-packings and the associated graph parameters $k$-tuple domination number and $2$-packing number. In particular, we determine the Kneser graphs $K(n,r)$ with $k$-tuple domination number exactly $k+r$ and find all the minimum sized $k$-tuple dominating sets for these graphs, which generalize results for dominating sets in Kneser graphs. Besides, we give a characterization of the $k$-tuple dominating sets of $K(n,2)$ in terms of the occurrences of the elements in $[n]$, which allows us to obtain minimum sized $k$-tuple dominating sets for almost all positive integers $n\\geq 4$. Finally, we compute both parameters for certain Kneser graphs, and specifically in odd graphs we show that these invariants are extremely related with perfect $1$-codes and Steiner systems. Keywords: Kneser graphs, $k$-tuple dominating set.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-08-29T19:50:17.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "kneser graphs",
      "tuple dominating set",
      "tuple domination number",
      "associated graph parameters",
      "odd graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}