{
  "id": "2206.07208",
  "version": "v1",
  "published": "2022-06-14T23:33:09.000Z",
  "updated": "2022-06-14T23:33:09.000Z",
  "title": "Partial Domination and Irredundance Numbers in Graphs",
  "authors": [
    "Pawaton Kaemawichanurat",
    "Odile Favaron"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A dominating set of a graph $G=(V,E)$ is a vertex set $D$ such that every vertex in $V(G) \\setminus D$ is adjacent to a vertex in $D$. The cardinality of a smallest dominating set of $D$ is called the domination number of $G$ and is denoted by $\\gamma(G)$. A vertex set $D$ is a $k$-isolating set of $G$ if $G - N_{G}[D]$ contains no $k$-cliques. The minimum cardinality of a $k$-isolating set of $G$ is called the $k$-isolation number of $G$ and is denoted by $\\iota_{k}(G)$. Clearly, $\\gamma(G) = \\iota_{1}(G)$. A vertex set $I$ is irredundant if, for every non-isolated vertex $v$ of $G[I]$, there exists a vertex $u$ in $V \\setminus I$ such that $N_{G}(u) \\cap I = \\{v\\}$. An irredundant set $I$ is maximal if the set $I \\cup \\{u\\}$ is no longer irredundant for any $u \\in V(G) \\setminus I$. The minimum cardinality of a maximal irredundant set is called the irredundance number of $G$ and is denoted by $ir(G)$. Allan and Laskar \\cite{AL1978} and Bollob\\'{a}s and Cockayne \\cite{BoCo1979} independently proved that $\\gamma(G) < 2ir(G)$, which can be written $\\iota_1(G) < 2ir(G)$, for any graph $G$. In this paper, for a graph $G$ with maximum degree $\\Delta$, we establish sharp upper bounds on $\\iota_{k}(G)$ in terms of $ir(G)$ for $\\Delta - 2 \\leq k \\leq \\Delta + 1$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-06-14T23:33:09.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "irredundance number",
      "partial domination",
      "vertex set",
      "minimum cardinality",
      "maximal irredundant set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}