Partial domination and irredundance numbers in graphs
Journal article
Authors/Editors
Strategic Research Themes
Publication Details
Author list: Pawaton Kaemawichanurat, Odile Favaron
Publisher: Elsevier
Publication year: 2023
Volume number: 457
Start page: 128153
ISSN: 0096-3003
eISSN: 1873-5649
URL: https://www.sciencedirect.com/science/article/pii/S0096300323003223?via%3Dihub
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$.
%Damaschke \cite{D} reduced the upper bound to be $3ir(G)/2$ when %the graph is a tree. The upper bound $3ir(G)/2$ was proved to be %true by Volkmann \cite{V} even when the graphs are in some tree-%like classes. In the same paper, Volkmann conjectured that, if
%$G$ is a cactus (a graph such that each edge is contained in at %most one cycle), then $\gamma(G) < 8ir(G)/5$. This conjecture was %proved by V. E. Zverovich \cite{Z}.
%seven years later.
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$.
Keywords
No matching items found.