Search

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$.

For a graph $G$, a vertex subset $S \subseteq V(G)$ is said to be $K_{k}$-isolating if $G - N_{G}[S]$ does not contain $K_{k}$ as a subgraph. The $K_{k}$-isolation number of $G$, denoted by $\iota_{k}(G)$, is the minimum cardinality of a $K_{k}$-isolating set of $G$. Analogously, $S$ is said to be independent $K_{k}$-isolating if $S$ is a $K_{k}$-isolating set of $G$ and $G[S]$ has no edge. The independent $K_{k}$-isolation number of $G$, denoted by $\iota'_{k}(G)$, is the minimum cardinality of an independent $K_{k}$-isolating set of $G$. Clearly, when $k = 1$, we have $\gamma(G) = \iota_{1}(G)$ and $i(G) = \iota'_{1}(G)$ where $\gamma(G)$ and $i(G)$ are the domination and independent domination numbers. For classic results between $\gamma(G)$ and $i(G)$, in 1978, Allan and Laskar proved that $\gamma(G) = i(G)$ for all $K_{1, 3}$-free graphs and this result was generalized to $K_{1, r}$-free graphs by Bollob$\acute{a}$s and Cockayne in 1979. In 2013, Rad and Volkmann proved that the ratio $i(G)/\gamma(G)$ is at most $\Delta(G)/2$ when $\Delta(G) \in \{3, 4, 5\}$. Further, Furuya et. al. proved that when $\Delta(G) \geq 6$, we have $i(G)/\gamma(G) \leq \Delta(G) - 2\sqrt{\Delta(G)} + 2$. In this paper, for a smallest $K_{k}$-isolating set $S$, we prove that $\iota'_k(G)\le -\frac{\iota_k^2(G)}{\ell} +i_k(G)(\Delta +2)-\ell \Delta$ where $\ell$ is the number of some specific vertices of $S$ such that the union of their closed neighborhoods in $S$ is $S$. We prove that this bound is sharp. A special case of our main theorem implies $\iota'_{k}(G)/\iota_{k}(G) \leq \Delta(G) - 2\sqrt{\Delta(G)} + 2$. Further, we find an inequality between $\iota'_{k}(G)$ and $\iota_{k}(G)$ when $G$ is $K_{1, r}$-free graph. This also generalizes the result of Bollob$\acute{a}$s and Cockayne.