{
  "id": "2312.15464",
  "version": "v1",
  "published": "2023-12-24T11:50:39.000Z",
  "updated": "2023-12-24T11:50:39.000Z",
  "title": "$k$-Domination invariants on Kneser graphs",
  "authors": [
    "Boštjan Brešar",
    "María Gracia Cornet",
    "Tanja Dravec",
    "Michael A. Henning"
  ],
  "comment": "15 pages, 3 tables",
  "categories": [
    "math.CO"
  ],
  "abstract": "In this follow-up to [M.G.~Cornet, P.~Torres, arXiv:2308.15603], where the $k$-tuple domination number and the 2-packing number in Kneser graphs $K(n,r)$ were studied, we are concerned with two variations, the $k$-domination number, ${\\gamma_{k}}(K(n,r))$, and the $k$-tuple total domination number, ${\\gamma_{t\\times k}}(K(n,r))$, of $K(n,r)$. For both invariants we prove monotonicity results by showing that ${\\gamma_{k}}(K(n,r))\\ge {\\gamma_{k}}(K(n+1,r))$ holds for any $n\\ge 2(k+r)$, and ${\\gamma_{t\\times k}}(K(n,r))\\ge {\\gamma_{t\\times k}}(K(n+1,r))$ holds for any $n\\ge 2r+1$. We prove that ${\\gamma_{k}}(K(n,r))={\\gamma_{t\\times k}}(K(n,r))=k+r$ when $n\\geq r(k+r)$, and that in this case every ${\\gamma_{k}}$-set and ${\\gamma_{t\\times k}}$-set is a clique, while ${\\gamma_{k}}(r(k+r)-1,r)={\\gamma_{t\\times k}}(r(k+r)-1,r)=k+r+1$, for any $k\\ge 2$. Concerning the 2-packing number, $\\rho_2(K(n,r))$, of $K(n,r)$, we prove the exact values of $\\rho_2(K(3r-3,r))$ when $r\\ge 10$, and give sufficient conditions for $\\rho_2(K(n,r))$ to be equal to some small values by imposing bounds on $r$ with respect to $n$. We also prove a version of monotonicity for the $2$-packing number of Kneser graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-12-24T11:50:39.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "05D05"
    ],
    "keywords": [
      "kneser graphs",
      "domination invariants",
      "tuple total domination number",
      "tuple domination number",
      "sufficient conditions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}