Restrained Italian domination in trees

Abstract

Let $G=(V,E)$ be a graph. A subset D of V is a restrained dominating set if every vertex in $V\setminus D$ is adjacent to a vertex in D and to a vertex in $V\setminus D$. The restrained domination number, denoted by ${\gamma }_r(G)$, is the smallest cardinality of a restrained dominating set of G. A function $f:V\to \{0,1,2\}$ is a restrained Italian dominating function on G if (i) for each vertex $v\in V$ for which $f(v)=0$, it holds that $\sum _{u\in N_G(v)}f(u)\ge 2$, (ii) the subgraph induced by $\{v\in V\mid f(v)=0\}$ has no isolated vertices. The restrained Italian domination number, denoted by ${\gamma }_{rI}(G)$, is the minimum weight taken over all restrained Italian dominating functions of G. It is known that ${\gamma }_r(G)\le {\gamma }_{rI}(G)\le 2{\gamma }_r(G)$ for any graph G. In this paper, we characterize the trees T for which ${\gamma }_r(T)={\gamma }_{rI}(T)$, and we also characterize the trees T for which ${\gamma }_{rI}(T)=2{\gamma }_r(T)$.

Keywords:

• Restrained domination
• restrained Italian domination
• tree

Acknowledgments

We are grateful to the anonymous reviewers for their comments.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This research was supported by Basic Science Research Program through the National Research Foundation of Korea funded by the Ministry of Education (2020R1I1A1A01055403).