Abstract
A 2-rainbow dominating function (2RDF) on a graph \(G=(V, E)\) is a function f from the vertex set V to the set of all subsets of the set \(\{1,2\}\) such that for any vertex \(v\in V\) with \(f(v)=\emptyset \) the condition \(\bigcup _{u\in N(v)}f(u)=\{1,2\}\) is fulfilled. A 2RDF f is independent (I2RDF) if no two vertices assigned nonempty sets are adjacent. The weight of a 2RDF f is the value \(\omega (f)=\sum _{v\in V}|f (v)|\). The 2-rainbow domination number \(\gamma _{r2}(G)\) (respectively, the independent 2-rainbow domination number \(i_{r2}(G)\)) is the minimum weight of a 2RDF (respectively, I2RDF) on G. We say that \(\gamma _{r2}(G)\) is strongly equal to \(i_{r2}(G)\) and denote by \(\gamma _{r2}(G)\equiv i_{r2}(G)\), if every 2RDF on G of minimum weight is an I2RDF. In this paper, we provide a constructive characterization of trees T with \(\gamma _{r2}(T)\equiv i_{r2}(T)\).
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Let G be a simple graph with vertex set \(V=V(G)\) and edge set \(E=E(G)\). For every vertex \(v\in V\), the open neighborhood N(v) is the set \(\{u\in V\mid uv\in E\}\) and the closed neighborhood of v is the set \(N[v] = N(v) \cup \{v\}\). The degree of a vertex \(v\in V\) is \(\deg _G(v)=\deg (v)=|N(v)|\). If \(A\subseteq V(G)\), then G[A] is the subgraph induced by A. A vertex of degree one is called a leaf, and its neighbor is called a support vertex. If v is a support vertex, then \(L_v\) will denote the set of all leaves adjacent to v. A support vertex v is called strong support vertex if \(|L_v|>1\). For \(r,s\ge 1\), a double star S(r, s) is a tree with exactly two vertices that are not leaves, with one adjacent to r leaves and the other to s leaves. For a vertex v in a rooted tree T, let C(v) denote the set of children of v, D(v) denote the set of descendants of v and \(D[v]=D(v)\cup \{v\}\), and the depth of v, \(\mathrm{depth}(v)\), is the largest distance from v to a vertex in D(v). The maximal subtree at v is the subtree of T induced by \(D(v) \cup \{v\}\) and is denoted by \(T_v\). For terminology and notation on graph theory not given here, the reader is referred to [11, 13].
For a positive integer k, a k-rainbow dominating function (kRDF) of a graph G is a function f from the vertex set V(G) to the set of all subsets of the set \(\{1,2,\ldots ,k\}\) such that for any vertex \(v\in V(G)\) with \(f(v)=\emptyset \) the condition \(\bigcup _{u\in N(v)}f(u)=\{1,2,\ldots ,k\}\) is fulfilled. The weight of a kRDF f is the value \(\omega (f)=\sum _{v\in V}|f (v)|\). The k-rainbow domination number of a graph G, denoted by \(\gamma _{rk}(G)\), is the minimum weight of a kRDF of G. A \(\gamma _{rk}(G)\)-function is a k-rainbow dominating function of G with weight \(\gamma _{rk}(G)\). Note that \(\gamma _{r1}(G)\) is the classical domination number \(\gamma (G)\). The k-rainbow domination number was introduced by Bre\(\check{\mathrm{s}}\)ar, Henning and Rall [3] and has been studied by several authors (see, e.g., [4–7, 12]). To study other domination parameters, we refer the readers to [1, 2, 14, 15].
A k-rainbow dominating function f is called an independent k-rainbow dominating function (abbreviated IkRDF) on G if the set \(V(G)-\{v\in V\mid f(v)=\emptyset \}\) is independent. The independent k-rainbow domination number, denoted by \(i_{rk}(G)\), is the minimum weight of an IkRDF on G. An independent k-rainbow dominating function f is called an \(i_{rk}(G)\)-function if \(\omega (f)=i_{rk}(G)\). Since each independent k-rainbow dominating function is a k-rainbow dominating function, we have \(\gamma _{rk}(G)\le i_{rk}(G)\).
Clearly if \(\gamma _{rk}(G)= i_{rk}(G)\), then every \(i_{rk}(G)\)-function is also a \(\gamma _{rk}(G)\)-function. However, not every \(\gamma _{rk}(G)\)-function is an \(i_{rk}(G)\)-function, even when \(\gamma _{rk}(G)= i_{rk}(G)\). For example, the double star \(S(k,k+1)\) has two \(\gamma _{rk}(S(k,k+1))\)-function, but only one of them is an \(i_{rk}(S(k,k+1))\)-function. We say that \(\gamma _{rk}(G)\) and \(i_{rk}(G)\) are strongly equal and denote by \(\gamma _{rk}(G)\equiv i_{rk}(G)\), if every \(\gamma _{rk}(G)\)-function is an \(i_{rk}(G)\)- function.
Haynes and Slater in [10] were the first to introduce strong equality between two parameters. Also in [8, 9], Haynes, Henning and Slater gave constructive characterizations of trees with strong equality between some domination parameters.
Our purpose in this paper is to present a constructive characterizations of trees T with \(\gamma _{r2}(T)\equiv i_{r2}(T)\).
We make use of the following result in this paper.
Proposition A
[5] Let G be a connected graph. If there is a path \(v_3v_2v_1\) in G with \(\deg (v_2)=2\) and \(\deg (v_1)=1\), then G has a \(\gamma _{r2}(G)\)-function f such that \(f(v_1)=\{1\}\) and \(2\in f(v_3)\).
Corollary 1
Let T be a tree with \(\gamma _{r2}(T)\equiv i_{r2}(T)\). If there is a path \(v_3v_2v_1\) in T with \(\deg (v_2)=2\) and \(\deg (v_1)=1\) such that \(v_3\) is a support vertex, then T has a \(\gamma _{r2}(T)\)-function f such that \(f(v_3)=\{1,2\}\), \(|f(v_1)|=1\) and \(|f(x)|=0\) for every \(x\in L_{v_3}\cup \{v_2\}\).
Observation 2
Let T be a tree and let z be a strong support vertex of T. Then
-
(a)
T has a \(\gamma _{r2}(T)\)-function such that \(f(z)=\{1,2\}\).
-
(b)
\(\gamma _{r2}(T)\not \equiv i_{r2}(T)\) if and only if T has a \(\gamma _{r2}(T)\)-function that is not independent and \(f(z)=\{1,2\}\).
Proof
(a) The proof is immediate.
(b) Let \(\gamma _{r2}(T)\not \equiv i_{r2}(T)\). Then T has a \(\gamma _{r2}(T)\)-function that is not independent. If \(f(z)=\{1,2\}\), then we are done. If \(|f(z)|=1\), then \(|f(x)|=1\) for each \(x\in L_z\) and the function \(g:V(G)\rightarrow {\mathcal {P}}(\{1,2\})\) defined by \(g(z)=\{1,2\}, g(x)=\emptyset \) for \(x\in L_z\) and \(g(u)=f(u)\) otherwise, is a 2RDF of T of weight less than \(\omega (f)\) which is a contradiction. Let \(f(z)=\emptyset \). Then clearly the function \(g:V(G)\rightarrow {\mathcal {P}}(\{1,2\})\) defined by \(g(z)=\{1,2\}, g(x)=\emptyset \) for \(x\in L_z\) and \(g(u)=f(u)\) otherwise, is a \(\gamma _{r2}(T)\)-function with the desired property. \(\square \)
2 Characterizations of Trees with \(\gamma _{r2}(T)\equiv i_{r2}(T)\)
Let \({\mathcal {F}}_1\) be the family of trees that can be obtained from \(k\ge 1\) disjoint stars \(K_{1,2}\) by adding either a new vertex v or a path uv and joining the centers of stars to v. Also let \({\mathcal {F}}_2\) be the family including \(P_5\) and all trees obtained from \(k\ge 2\) disjoint \(P_3\) by adding either a new vertex v or a path uv and joining v to a leaf of each \(P_3\). If T belongs to \({\mathcal {F}}_1 \cup {\mathcal {F}}_2-\{P_5\}\), then we call the vertex v, the special vertex of T and if \(T=P_5\), then its support vertices are special vertices of T. Note that if \(T\in {\mathcal {F}}_1 \cup {\mathcal {F}}_2\), then \(\gamma _{r2}(T)\equiv i_{r2}(T)\).
Now we provide a constructive characterization of trees T with \(\gamma _{r2}(T)\equiv i_{r2}(T)\). For this purpose, we define a family of trees as follows: Let \({\mathcal {F}}\) be the family of trees such that: \({\mathcal {F}}\) contains star \(K_{1,2}\) and if T is a tree in \({\mathcal {F}}\), then the tree \(T'\) obtained from T by the following seven operations which extend the tree T by attaching a tree to a vertex \(y\in V (T)\), called an attacher, is also a tree in \({\mathcal {F}}\).
-
Operation \({\mathcal {O}}_1\): If z is a strong support vertex of \(T\in {{\mathcal {F}}}\), then \(\mathcal {O}_1\) adds a new vertex x and an edge xz.
-
Operation \({\mathcal {O}}_2\): If z is a vertex of \(T\in {{\mathcal {F}}}\), then \({\mathcal {O}}_2\) adds a new tree \(T_1\in {\mathcal {F}}_1\) with special vertex x and an edge xz provided that if x is a support vertex, then \(\gamma _{r2}(T-z)\ge \gamma _{r2}(T)\).
-
Operation \({\mathcal {O}}_3\): If z is a strong support vertex of \(T\in {{\mathcal {F}}}\), then \({\mathcal {O}}_3\) adds a path zxy.
-
Operation \({\mathcal {O}}_4\): If z is a vertex of \(T\in {{\mathcal {F}}}\) which is adjacent to a support vertex of degree 2, then \({\mathcal {O}}_4\) adds a path zxy.
-
Operation \({\mathcal {O}}_5\): If z is a vertex of \(T\in {\mathcal {F}}\) which is adjacent to a strong support vertex, then \({\mathcal {O}}_5\) adds a path zxyw.
-
Operation \({\mathcal {O}}_6\): If z is a vertex of \(T\in {\mathcal {F}}\), then \({\mathcal {O}}_6\) adds a new tree \(T_2\in {\mathcal {F}}_2\) with special vertex x and an edge xz provided that if x is a support vertex, then \(\gamma _{r2}(T-z)\ge \gamma _{r2}(T)\).
-
Operation \({\mathcal {O}}_7\): If z is a vertex of \(T\in {{\mathcal {F}}}\) such that every \(\gamma _{r2}(T)\)-function assigns \(\emptyset \) to z, then \({\mathcal {O}}_7\) adds the double star S(1, 2) and an edge zx where x is a leaf of S(1, 2) whose support vertex has degree 3.
Observation 3
The family \({{\mathcal {F}}}\) contains all graphs in \(\{K_{1,t}\mid t\ge 2\}\cup {{\mathcal {F}}}_1\cup {{\mathcal {F}}}_2\).
Proof
Starting from \(K_{1,2}\in {{\mathcal {F}}}\) and by applying \(t-2\) times Operation \({{\mathcal {O}}}_1\), we obtain the star \(K_{1,t}\) and hence \({{\mathcal {F}}}\) contains all stars. Furthermore, starting from \(K_{1,2}\) and by applying Operation \({{\mathcal {O}}}_4\), we obtain that \({{\mathcal {F}}}\) contains \(P_5\).
Now let \(T\in {{\mathcal {F}}}_1\). If \(|V(T)|=4\), then \(T=K_{1,3}\) and immediately \(T\in {{\mathcal {F}}}\). If \(|V(T)|=5\), then T can be obtained from \(K_{1,2}\) by applying Operation \({{\mathcal {O}}}_3\). If \(|V(T)|\ge 6\), then T can be obtained from \(K_{1,2}\) by applying Operation \({{\mathcal {O}}}_2\). Thus \({{\mathcal {F}}}\) contains all graphs in \({{\mathcal {F}}}_1\).
Finally, let \(T\in {{\mathcal {F}}}_2-\{P_5\}\). If \(|V(T)|=7\), then \(T=P_7\) and T can be obtained from \(P_5\) by applying Operation \(\mathcal O_4\) twice and so \(T\in {{\mathcal {F}}}\). If \(|V(T)|\ge 9\), then T can be obtained from \(K_{1,2}\) by applying Operation \({{\mathcal {O}}}_6\). Thus \({{\mathcal {F}}}\) contains all graphs in \({{\mathcal {F}}}_2\). \(\square \)
Lemma 4
Let T be a tree with \(\gamma _{r2}(T)\equiv i_{r2}(T)\) and let \(T'\) be the tree obtained from T by Operation \({\mathcal {O}}_1\). Then \(\gamma _{r2}(T')\equiv i_{r2}(T')\).
Proof
Assume z is a strong support vertex of T and let x be a new vertex that is attached to z by applying Operation \({\mathcal {O}}_1\). By Observation 2(a), T has a \(\gamma _{r2}\)-function f that assigns \(\{1,2\}\) to z. Since \(\gamma _{r2}(T)\equiv i_{r2}(T)\), f is an I2RDF of T. Now we can extend f to an I2RDF of \(T'\) by assigning \(\emptyset \) to x, implying that \(\gamma _{r2}(T')\le i_{r2}(T')\le i_{r2}(T)\le \gamma _{r2}(T)\). On the other hand, by Observation 2(a), there is a \(\gamma _{r2}(T')\)-function g which assigns \(\{1,2\}\) to z, and clearly the function g, restricted to T, is a 2RDF of T of weight \(\gamma _{r2}(T')\), implying that \(\gamma _{r2}(T)\le \gamma _{r2}(T')\). Hence \(\gamma _{r2}(T')=i_{r2}(T')\).
It will now be shown that \(\gamma _{r2}(T')\equiv i_{r2}(T')\). Suppose h is a \(\gamma _{r2}(T')\)-function that is not independent. Since \(|L_{z}|\ge 3\), we must have \(f(z)=\{1,2\}\). Then the function h, restricted to T, is a \(\gamma _{r2}(T)\)-function that is not independent which leads to a contradiction. Thus \(\gamma _{r2}(T')\equiv i_{r2}(T)\). \(\square \)
Lemma 5
Let T be a tree with \(\gamma _{r2}(T)\equiv i_{r2}(T)\) and let \(T'\) be a tree obtained from T by Operation \({\mathcal {O}}_2\). Then \(\gamma _{r2}(T')\equiv i_{r2}(T')\).
Proof
Let \(T_1\in {\mathcal {F}}_1\) be the tree which is attached by Operation \({\mathcal {O}}_2\) to T by the edge xz for obtaining the tree \(T'\), where \(z\in V(T)\) is the attacher vertex, and let \(x_{1}, x_{2},\ldots ,x_{k}\in V(T_1)\) be the strong support vertices of \(T_1\). Assume x is the special vertex of \(T_1\). If x is a support vertex then let y be the leaf that is adjacent to x. Let t be a variant defined by \(t=1\) if x is a support vertex, and \(t=0\) otherwise. Every \(i_{r2}(T)\)-function can be extended to an I2RDF on \(T'\) by assigning \(\{1,2\}\) to \(x_i\), \(i=1,2,\ldots ,k\), \(\emptyset \) to u for \(u\in \cup _{i=1}^kN(x_i)\), and \(\{1\}\) to y if x is a support vertex. This implies that \(i_{r2}(T')\le i_{r2}(T)+2k+t\). Since \(\gamma _{r2}(T)\equiv i_{r2}(T)\), we deduce that
Now we show that \(\gamma _{r2}(T')= \gamma _{r2}(T)+2k+t\). Let f be a \(\gamma _{r2}(T')\)-function. It is easy to see that \(\sum _{u \in N[x_i]-\{x\}}|f(u)|\ge 2\), for \(i=1,2,\ldots ,k\), and \(|f(x)|+|f(y)|\ge 1\), if \(t=1\). Then \(\sum _{u\in V(T_1)}|f(u)|\ge 2k+t\). If \(|f(x)|=0\) then \(f|_{V(T)}\) is a 2RDF on T, and so \(\sum _{u\in V(T)}|f(u)|\ge \gamma _{r2}(T)\). By adding two recent inequalities, we obtain \(\gamma _{r2}(T')= \sum _{u\in V(T')}|f(u)|\ge \gamma _{r2}(T)+2k+t.\) Assume that \(|f(x)|\ge 1\). Clearly if \(t=1\) then \(|f(x)|+|f(y)|\ge 2\). Thus \(\sum _{u\in V(T_1)}|f(u)|\ge 2k+t+1\). If \(|f(z)|\ne 0\) then \(f|_{V(T)}\) is a 2RDF on T, and if \(|f(z)|= 0\) then the function \(f_1\) defined on V(T) by \(f_1(z)=\{1\}\) and \(f_1(u)=f(u)\) if \(u\in V(T)-\{z\}\) is a 2RDF for T. It follows that \(\gamma _{r2}(T')\ge \gamma _{r2}(T)+2k+t.\) Hence, we deduce that
It will now be shown that \(\gamma _{r2}(T')\equiv i_{r2}(T')\). Assume h is a \(\gamma _{r2}(T')\)-function that is not independent. We may assume that h assigns \(\{1,2\}\) to each support vertex adjacent to x. If \(|h(x)|=0\) then clearly \(h|_{V(T)}\) is a \(\gamma _{r2}(T)\)-function that is not independent, a contradiction with the assumption \(\gamma _{r2}(T)\equiv i_{r2}(T)\). Thus \(|h(x)|\ge 1\). Then \(|h(z)|=0\) and \(\sum _{v\in V(T_1)}|h(v)|\ge 2k+1+t\). If \(|h(x)|=1\), then \(\sum _{w\in N_{T}(z)}|h(w)|\ge 1\) and the function \(g:V(T)\rightarrow {{\mathcal {P}}}(\{1,2\})\) defined by \(g(z)=\{1\}\) and \(g(u)=h(u)\) for \(u\in V(T)-\{z\}\) is a \(\gamma _{r2}(T)\)-function that is not independent, contradicting \(\gamma _{r2}(T)\equiv i_{r2}(T)\). Thus \(|h(x)|=2\). Then x is a support vertex. Now
This is a contradiction with the assumption \(\gamma _{r2}(T-z)\ge \gamma _{r2}(T)\). Therefore, \(\gamma _{r2}(T^{\prime })\equiv i_{r2}(T^{\prime })\) and the proof is complete. \(\square \)
Lemma 6
If T is a tree with \(\gamma _{r2}(T)\equiv i_{r2}(T)\) and \(T'\) is a tree obtained from T by Operation \({\mathcal {O}}_3\), then \(\gamma _{r2}(T')\equiv i_{r2}(T')\).
Proof
Let \(z\in V(T)\) be a strong support vertex and let zxy be the path added by Operation \({\mathcal {O}}_3\) to obtain \(T'\). Let f be a \(\gamma _{r2}(T)\)-function such that \(f(z)=\{1,2\}\) [Observation 2(a)]. Since \(\gamma _{r2}(T)\equiv i_{r2}(T)\), f is an I2RDF of T. We can extend f to an I2RDF on \(T'\) by assigning \(\emptyset \) to x and \(\{1\}\) to y, and thus
Let now \(f_1\) be a \(\gamma _{r2}(T')\)-function. We can assume \(f_1(z)=\{1,2\}\) by Observation 2(a). Since \(f_1\) is a \(\gamma _{r2}(T')\)-function, we must have \(|f_1(x)|=0\) and \(|f_1(y)|=1\). Then \(f_1|_{V(T)}\) is a 2RDF on T, and so
It follows from (3) and (4) that \(\gamma _{r2}(T')= i_{r2}(T')= \gamma _{r2}(T)+1=i_{r2}(T)+1.\)
Finally, we shall show that \(\gamma _{r2}(T')\equiv i_{r2}(T')\). Assume h is a \(\gamma _{r2}(T')\)-function that it is not independent. First let \(|h(x)|\ge 1\). Then \(|h(x)|+|h(y)|=2\). If \(|h(z)|\ne 0\) then replace h(x) by \(\emptyset \) and h(y) by \(\{1\}\) or \(\{2\}\) to obtain a 2RDF for \(T'\) of weight less than \(\gamma _{r2}(T')\), a contradiction. Thus \(|h(z)|=0\). Then clearly \(|h(u)|=1\) for any leaf u adjacent to z and the function \(h_1:V(T')\rightarrow {{\mathcal {P}}}(\{1,2\})\) defined by \(h_1(y)=\{1\}, h_1(z)=\{1,2\}, h_1(u)=\emptyset \) for \(u\in L_z\cup \{x\}\) and \(h_1(w)=h(w)\) otherwise, is a 2RDF for \(T'\) of weight less than \(\gamma _{r2}(T')\), a contradiction. Now let \(|h(x)|=0\). Then clearly \(|h(y)|=1\) (else we could make a change to be in the previous case \(|h(x)|\ge 1\)), and \(h|_{V(T)}\) is a \(\gamma _{r2}(T)\)-function which is not independent, a contradiction. Hence, \(\gamma _{r2}(T')\equiv i_{r2}(T')\). This completes the proof. \(\square \)
Lemma 7
If T is a tree with \(\gamma _{r2}(T)\equiv i_{r2}(T)\) and \(T'\) is a tree obtained from T by Operation \({\mathcal {O}}_4\), then \(\gamma _{r2}(T')\equiv i_{r2}(T')\).
Proof
Let \(z\in V(T)\) be a vertex which is adjacent to a support vertex of degree 2 such as w, and let Operation \({\mathcal {O}}_4\) add the path zxy to T.
First let \(\deg _T(z)\ge 2\). Let \(w'\) be the leaf adjacent to w. Assume f is a \(\gamma _{r2}(T)\)-function such that \(2\in f(z)\) (Proposition A). Since \(\gamma _{r2}(T)\equiv i_{r2}(T)\), f is an \(i_{r2}(T)\)-function. Now f can be extended to an I2RDF on \(T'\) by assigning \(\emptyset \) to x and \(\{1\}\) to y. Thus
On the other hand, if \(f_1\) is a \(\gamma _{r2}(T')\)-function, then we may assume that \(2\in f_1(z)\) by Proposition A. Clearly \(|f_1(x)|+|f_1(y)|\ge 1\) and \(f_1|_{V(T)}\) is a 2RDF on T of weight at most \(\gamma _{r2}(T')-1\), implying that \(\gamma _{r2}(T')\ge \gamma _{r2}(T)+1\). It follows from (5) and the recent inequality that \(\gamma _{r2}(T')= i_{r2}(T')= i_{r2}(T)+1=\gamma _{r2}(T)+1.\)
It will now be shown that \(\gamma _{r2}(T')\equiv i_{r2}(T')\). Suppose h is a \(\gamma _{r2}(T')\)-function which it is not independent. If \(|h(z)|> 0\) then we must have \(|h(x)|=0\) and \(|h(y)|=1\), and so \(h|_{V(T)}\) is a \(\gamma _{r2}(T)\)-function which is not independent, a contradiction. Let \(|h(z)|=0\). Then obviously \(|h(x)|+|h(y)|=|h(w)|+|h(w')|=2\). Then the function \(g:V(T')\rightarrow {{\mathcal {P}}}(\{1,2\})\) defined by \(g(x)=g(w)=\emptyset \), \(g(y)=g(w')=\{1\}, g(z)=\{2\}\) and \(g(u)=f(u)\) for \(u\in V(T')-\{x,y,w,w',z\}\), is a 2RDF of \(T'\) of weight less than \(\gamma _{r2}(T')\), a contradiction. Thus \(\gamma _{r2}(T')\equiv i_{r2}(T')\).
Now let \(\deg _T(z)=1\), i.e., z is a leaf.
Assume f is a \(\gamma _{r2}(T)\)-function. By Proposition A, we may assume that \(f(z)=\{1\}\). Note that f is an \(i_{r2}(T)\)-function because \(\gamma _{r2}(T)\equiv i_{r2}(T)\). Then f can be extended to an I2RDF on \(T'\) by assigning \(\emptyset \) to x and \(\{2\}\) to y. This implies that
On the other hand, if \(f_1\) is a \(\gamma _{r2}(T')\)-function, then by Proposition A we may assume \(f_1(y)=\{1\}\) and \(2\in f_1(z)\). Then \(f_1|_{V(T)}\) is a 2RDF of T of weight at most \(\gamma _{r2}(T')-1\), implying that \(\gamma _{r2}(T')\ge \gamma _{r2}(T)+1\). It follows from the last inequality and (6) that \(\gamma _{r2}(T')= i_{r2}(T')= \gamma _{r2}(T)+1=i_{r2}(T)+1\).
Next we show that \(\gamma _{r2}(T')\equiv i_{r2}(T')\). Assume h is a \(\gamma _{r2}(T')\)-function that it is not independent. If \(|h(z)|> 0\) then we may assume that \(|h(x)|=0\) and \(|h(y)|=1\), and so \(h|_{V(T)}\) is a \(\gamma _{r2}(T)\)-function which is not independent, a contradiction. Let \(h(z)=\emptyset \). Then \(|h(x)|+|h(y)|\ge 2\). If \(|h(w)|=0\) then \(|h(x)|=2\) and \(|h(y)|=0\), and the function \(h_1:V(T)\rightarrow {{\mathcal {P}}}(\{1,2\})\) defined by \(h_1(z)=\{1\}\) and \(h_1(u)=h(u)\) if \(u\in V(T)-\{z\}\) is a \(\gamma _{r2}(T)\)-function which is not independent, a contradiction. If \(|h(w)|\ge 1\) then it follows from \(|h(x)|+|h(y)|\ge 2\) that the function \(h_1:V(T)\rightarrow {{\mathcal {P}}}(\{1,2\})\) defined above, is a \(\gamma _{r2}(T)\)-function which is not independent, a contradiction. Hence \(\gamma _{r2}(T')\equiv i_{r2}(T')\). \(\square \)
Lemma 8
If T is a tree with \(\gamma _{r2}(T)\equiv i_{r2}(T)\) and \(T'\) is a tree obtained from T by Operation \({\mathcal {O}}_5\), then \(\gamma _{r2}(T')\equiv i_{r2}(T')\).
Proof
Let \(z\in V(T)\) be a vertex that has a strong support vertex u in its neighborhood and let Operation \({\mathcal {O}}_5\) add the path zxyw to T for obtaining \(T'\). Any 2RDF of T can be extended to a 2RDF for \(T'\) by assigning \(\{1,2\}\) to y, and \(\emptyset \) to x and w. Since \(\gamma _{r2}(T)\equiv i_{r2}(T)\), we deduce that
Let f be a \(\gamma _{r2}(T')\)-function. We may assume \(f(w)=\{1\}\), \(f(y)=\emptyset \) and \(2\in f(x)\), by Proposition A. Also we may assume that \(|f(u)|=2\), since u is a strong support vertex. Then \(f|_{V(T)}\) is a 2RDF on T of weight at most \(\gamma _{r2}(T')-2\), and so \(\gamma _{r2}(T)\le \gamma _{r2}(T')-2.\) It follows from (7) that
To show that \(\gamma _{r2}(T')\equiv i_{r2}(T')\), suppose h is a \(\gamma _{r2}(T')\)-function that it is not independent. Since u is a strong support vertex, we may assume \(|h(u)|=2\). Then clearly \(h(z)=\emptyset \) and \(|h(x)|+|h(y)|+|h(w)|=2\), and so \(h|_{V(T)}\) is a \(\gamma _{r2}(T)\)-function which is not independent, a contradiction. Hence \(\gamma _{r2}(T')\equiv i_{r2}(T')\) and the proof is completed. \(\square \)
The proof of next lemma is similar to the proof of Lemma 5, and therefore omitted.
Lemma 9
If T is a tree with \(\gamma _{r2}(T)\equiv i_{r2}(T)\), and \(T'\) is a tree obtained from T by Operation \({\mathcal {O}}_6\), then \(\gamma _{r2}(T)\equiv i_{r2}(T)\).
Lemma 10
If T is a tree with \(\gamma _{r2}(T)\equiv i_{r2}(T)\) and \(T'\) is a tree obtained from T by Operation \({\mathcal {O}}_7\), then \(\gamma _{r2}(T')\equiv i_{r2}(T')\).
Proof
Let z be a vertex of T such that every \(\gamma _{r2}(T)\)-function assign \(\emptyset \) to it, and let x be a leaf of double star S(1, 2) whose support vertex has degree 3. Assume that Operation \({\mathcal {O}}_7\) adds the double star S(1, 2) and the edge xz to obtain \(T'\) from T. Let \(V(S(1, 2))=\{x,v, v_0, u, u_0\}\) where \(N(v)=\{x,u,v_0\}\) and \(u\in N(u_0)\). Any 2RDF of T can be extended to a 2RDF on \(T'\) by assigning \(\emptyset \) to x, u and \(v_0\), \(\{1, 2\}\) to v and \(\{1\}\) to \(u_0\). Since \(\gamma _{r2}(T)\equiv i_{r2}(T)\), we deduce that
Let f be a \(\gamma _{r2}(T')\)-function such that \(f(u_0)=\{1\}\) and \(2\in f(v)\) by Observation A. Clearly \(|f(v)|+|f(u_0)|+|f(u)|+|f(v_0)|\ge 3\). We may assume that \(|f(x)|=0\), otherwise we replace f(x) by \(\emptyset \) and f(z) by \(f(z)\cup f(x)\). Then \(f|_{V(T)}\) is a 2RDF of T, implying that \(\gamma _{r2}(T)\le \gamma _{r2}(T')-3.\) By (8), we have \(\gamma _{r2}(T')= i_{r2}(T')= \gamma _{r2}(T)+3= i_{r2}(T)+3\).
It will now be shown that \(\gamma _{r2}(T')\equiv i_{r2}(T')\). Suppose h is a \(\gamma _{r2}(T')\)-function which is not independent. Clearly \(\sum _{y\in V(S(1, 2))}|h(y)|\ge 3\). If \(|h(z)|>0\), then \(h|_{V(T)}\) is a \(\gamma _{r2}(T)\)-function assigning nonempty set to z which leads to a contradiction. Thus \(|h(z)|=0\). If \(\sum _{y\in V(S(1, 2))}|h(y)|\ge 4\), then we change the values of h on \(V(S(1,2))\cup \{z\}\) to \(h(z)=h(u_0)=\{1\}\), \(h(v)=\{1,2\}\), and \(h(x)=h(u)=h(v_0)=\emptyset \), and then the new function plays the role of h which has been considered earlier. Thus we assume that \(\sum _{y\in V(S(1, 2))}|h(y)|=3\). Then clearly \(|h(x)|=0\), and \(h|_{V(T)}\) is a \(\gamma _{r2}(T)\)-function which is not independent, a contradiction. Hence \(\gamma _{r2}(T')\equiv i_{r2}(T')\). \(\square \)
Theorem 11
Each tree T in family \({\mathcal {F}}\cup \{K_1\}\) satisfies \(\gamma _{r2}(T)\equiv i_{r2}(T)\).
Proof
If \(T=K_1\), then clearly \(\gamma _{r2}(T)\equiv i_{r2}(T)\). Let \(T\in {{\mathcal {F}}}\). Then T is obtained from a star \(K_{1,2}\) by successive operations \({{{\mathcal {T}}}}^1,\ldots , {{{\mathcal {T}}}}^m\), where \({{{\mathcal {T}}}}^i\in \{{{{\mathcal {O}}}}_1,\ldots , {{{\mathcal {O}}}}_7\}\) if \(m\ge 1\) and \(T=K_{1,2}\) if \(m=0\). The proof is by induction on m. If \(m=0\), then clearly \(\gamma _{r2}(K_{1,2})\equiv i_{r2}(K_{1,2})\). Let \(m\ge 1\) and that the statement holds for all trees which are obtained from \(K_{1,2}\) by applying \(m-1\) operations in \(\{{{{\mathcal {O}}}}_1,\ldots ,{{{\mathcal {O}}}}_7\}\). It follows from Lemmas 4, ..., 10 that \(\gamma _{r2}(T)\equiv i_{r2}(T)\). \(\square \)
Observation 12
If S(p, q) is a double star with \(q\ge p\ge 1\) and \(\gamma _{r2}(S(p,q))\equiv i_{r2}(S(p,q))\), then \(p=1\) and \(q\ge 2\).
Theorem 13
Let T be a tree of order n. If \(\gamma _{r2}(T)\equiv i_{r2}(T)\), then \(T\in {\mathcal {F}}\cup \{K_1\}\).
Proof
The proof is by induction on n. If \(n=1\) then \(T=K_1\). Let the statement holds for all trees of order less than n and let T be a tree of order n with \(\gamma _{r2}(T)\equiv i_{r2}(T)\). Since \(\gamma _{r2}(P_2)\not \equiv i_{r2}(P_2)\), we may assume that \(n\ge 3\). If \(\mathrm{diam}(T)=2\) then T is a star and by Observation 3, \(T\in {{\mathcal {F}}}\). If \(\mathrm{diam}(T)=3\), then T is a double star S(p, q) with \(q\ge p\ge 1\). By Observation 12, we have \(p=1\) and \(q\ge 2\). Then T can be obtained from \(K_{1,q}\) by Operation \({\mathcal {O}}_3\) and so \(T\in {{\mathcal {F}}}\). Therefore, we may assume that \(\mathrm{diam}(T)\ge 4\).
Let \(v_1v_2\ldots v_k\;(k\ge 5)\) be a diametral path in T such that \(|L_{v_2}|\) is as large as possible and root T at \(v_k\). Also suppose among paths with this property we choose a path such that \(|L_{v_3}|\) is as large as possible.
Assume first that \(\deg (v_2)\ge 4\). Let f be a \(\gamma _{r2}(T)\)-function. Then clearly \(f(v_2)=\{1,2\}\) and so f is a 2RDF of \(T-v_1\). Since \(\gamma _{r2}(T)\equiv i_{r2}(T)\), f is also an I2RDF of \(T-v_1\), implying that \(\gamma _{r2}(T)=i_{r2}(T)\ge i_{r2}(T-v_1)\ge \gamma _{r2}(T-v_1)\). On the other hand, by Observation 2(a), \(T-v_1\) has a \(\gamma _{r2}\)-function g that assigns \(\{1,2\}\) to \(v_2\). Then g can be extended to a \(\gamma _{r2}(T)\)-function by assigning \(\emptyset \) to \(v_1\) that yields \(\gamma _{r2}(T)\le \gamma _{r2}(T-v_1)\). Hence \(\gamma _{r2}(T)=i_{r2}(T)= i_{r2}(T-v_1)=\gamma _{r2}(T-v_1).\)
We show that \(\gamma _{r2}(T-v_1)\equiv i_{r2}(T-v_1)\). Suppose that there is a \(\gamma _{r2}(T-v_1)\)-function g that is not independent. Since g is a \(\gamma _{r2}(T-v_1)\)-function, we must have \(|g(v_2)|+\sum _{u\in L_{v_2}-\{v_1\}}|g(u)|=2\). Now the function \(h:V(T-v_1)\rightarrow {{\mathcal {P}}}(\{1,2\})\) defined by \(h(v_2)=\{1,2\}, h(u)=\emptyset \) for \(u\in L_{v_2}-\{v_1\}\) and \(h(x)=g(x)\) otherwise, is a 2RDF of \(T-v_1\) which in not independent. It is clear that h can be extended to a \(\gamma _{r2}(T)\)-function which is not independent by assigning \(\emptyset \) to \(v_1\). This leads to a contradiction with \(\gamma _{r2}(T)\equiv i_{r2}(T)\). Thus \(\gamma _{r2}(T-v_1)\equiv i_{r2}(T-v_1)\). It follows from the inductive hypothesis that \(T-v_1\in {{\mathcal {F}}}\). Now it is clear that T can be obtained from \(T-v_1\in {\mathcal {F}}\) by applying Operation \({\mathcal {O}}_1\).
Assume next that \(\deg (v_2)=3\). Let \(u\in L_{v_2}-\{v_1\}\). We claim that \(v_3\) is not a strong support vertex. Assume to the contrary that \(v_3\) is a strong support vertex. By Observation 2(a), T has a \(\gamma _{r2}(T)\)-function f such that \(f(v_3)=\{1,2\}\). Clearly \(|f(v_2)|+|f(v_1)|+|f(u)|= 2\). Now the function \(g:V(T)\rightarrow {{\mathcal {P}}}(\{1,2\})\) defined by \(g(v_2)=\{1,2\}, g(v_1)=g(u)=\emptyset \) and \(g(x)=f(x)\) for \(x\in V(T)-\{u,v_1,v_2\}\) is clearly a \(\gamma _{r2}(T)\)-function that is not independent, a contradiction with \(\gamma _{r2}(T)\equiv i_{r2}(T)\). Thus \(v_3\) is not a strong support vertex. Using Proposition A and an argument similar to that described above, we deduce that \(v_3\) is not adjacent to a support vertex of degree 2. By the choice of the diametral path, we deduce that any child of \(v_3\) is a leaf or a support vertex of degree 3 and at most one of them is leaf. This implies that \(T_{v_3}\in \mathcal {F}_1\). Let \(T'=T-T_{v_3}\).
We claim that if \(v_3\) is a support vertex, then \(\gamma _{r2}(T'-v_4)\ge \gamma _{r2}(T')\). Let \(v_3\) be a support vertex and let to the contrary that \(\gamma _{r2}(T'-v_4)< \gamma _{r2}(T')\). Assume h is a \(\gamma _{r2}(T'-v_4)\)-function and define \(g: V(T)\rightarrow {{\mathcal {P}}}(\{1,2\})\) by \(g(x)=h(x)\) for \(x\in V(T')-\{v_4\}\), \(g(x)=\{1,2\}\) for \(x\in N[v_3]-(L_{v_3}\cup \{v_4\})\) and \(g(x)=\emptyset \) otherwise. Obviously g is a \(\gamma _{r2}(T)\)-function that is not independent, a contradiction with \(\gamma _{r2}(T)\equiv i_{r2}(T)\). Thus \(\gamma _{r2}(T'-v_4)\ge \gamma _{r2}(T')\) when \(v_3\) is a support vertex.
It will now be shown that \(\gamma _{r2}(T')\equiv i_{r2}(T')\). First we show that \(\gamma _{r2}(T')= i_{r2}(T')\). Since every \(\gamma _{r2}(T')\)-function can be extended to a 2RDF on T by assigning \(\{1, 2\}\) to the strong support vertices in \(N_{T_{v_3}}(v_3)\), \(\{1\}\) to the leaf adjacent to \(v_3\), if any, and \(\emptyset \) to the other vertices in \(T_{v_3}\), we deduce that
where k is the number of strong support vertices adjacent to \(v_3\) in \(T_{v_3}\) and t is the number of leaf adjacent to \(v_3\). On the other hand, let f be a \(\gamma _{r2}(T)\)-function. By Observation 2(a), we may assume that f assigns \(\{1, 2\}\) to the strong support vertices in \(T_{v_3}\). Since \(\gamma _{r2}(T)\equiv i_{r2}(T)\), f is an I2RDF. Then f assigns \(\emptyset \) to \(v_3\) and \(\{1\}\) or \(\{2\}\) to the leaf adjacent to \(v_3\), if any, and \(f|_{V(T')}\) is an I2RDF on \(T'\) with weight \(i_{r2}(T)-2k-t\). Thus \(i_{r2}(T')\le i_{r2}(T)-2k-t\). It follows from (9) that \(i_{r2}(T)=\gamma _{r2}(T)=\gamma _{r2}(T')+2k+t= i_{r2}(T')+2k+t\) and hence \(\gamma _{r2}(T')=i_{r2}(T')\).
Now we show that this equality is strong. Suppose h is a \(\gamma _{r2}(T')\)-function that it is not independent. We can extend h to a 2RDF on T by assigning \(\{1,2\}\) to every strong support vertex of \(T_{v_3}\) and \(\{1\}\) to the leaf adjacent to \(v_3\), if any, and \(\emptyset \) to the other vertices in \(T_{v_3}\), to obtain a \(\gamma _{r2}(T)\)-function which is not independent, a contradiction with \(\gamma _{r2}(T)\equiv i_{r2}(T)\). Therefore \(\gamma _{r2}(T')\equiv i_{r2}(T')\). It follows from the induction hypothesis that \(T'\in {\mathcal {F}}\). Then T can be obtained from \(T'\) by applying Operation \({\mathcal {O}}_2\) and hence \(T\in {\mathcal {F}}\).
We thus assume that \(\deg (v_2)=2\). Furthermore, we may assume that every child of \(v_3\) that is a support vertex has degree two. We now consider the following three cases on \(|L_{v_3}|\).
Case 1 \(|L_{v_3}|\ge 2\).
Let \(T'=T-\{v_1,v_2\}\). We show that \(\gamma _{r2}(T')\equiv i_{r2}(T')\). Suppose f is a \(\gamma _{r2}(T)\)-function that assigns \(\{1, 2\}\) to \(v_3\) [Observation 2(a)]. Clearly \(|f(v_1)|+|f(v_2)|=1\). Since \(\gamma _{r2}(T)\equiv i_{r2}(T)\), f is an \(i_{r2}(T)\)-function. Hence \(|f(v_2)|=0\) and \(f|_{V(T')}\) is an I2RDF on \(T'\) implying that
Now let g be a \(\gamma _{r2}(T')\)-function that assigns \(\{1,2\}\) to \(v_3\) [Observation 2(a)]. Then g can be extended to a 2RDF on T by assigning \(\emptyset \) to \(v_2\) and \(\{1\}\) to \(v_1\). This yields \(\gamma _{r2}(T)\le \gamma _{r2}(T')+1\), By (10), we have \(\gamma _{r2}(T')= i_{r2}(T')\). To show that this equality is strong, assume h is a \(\gamma _{r2}(T')\)-function that it is not independent. We may assume \(h(v_3)=\{1,2\}\). Now one can extend h to a \(\gamma _{r2}(T)\)-function which is not independent, by assigning \(\emptyset \) to \(v_2\) and \(\{1\}\) to \(v_1\), a contradiction with \(\gamma _{r2}(T)\equiv i_{r2}(T)\). Thus \(\gamma _{r2}(T')\equiv i_{r2}(T')\). By induction hypothesis, \(T'\in {\mathcal {F}}\) and so T can be obtain from \(T'\) by Operation \({\mathcal {O}}_3\).
Case 2 \(|L_{v_3}|=0\).
Then any child of \(v_3\) is a support vertex of degree 2. We consider two subcases.
Subcase 2.1 \(\deg (v_3)\ge 3\).
Let \(z_2\) be a child of \(v_3\) different from \(v_2\), and let \(z_1\) be the leaf adjacent to \(z_2\). Suppose \(T'=T-\{v_1,v_2\}\). We show that \(\gamma _{r2}(T')\equiv i_{r2}(T')\). Let f be a \(\gamma _{r2}(T)\)-function. We may assume \(2\in f(v_3)\) by Proposition A. Clearly \(|f(v_1)|+|f(v_2)|=1\). Since \(\gamma _{r2}(T)\equiv i_{r2}(T)\), f is a \(i_{r2}(T)\)-function. Clearly \(f|_{V(T')}\) is an I2RDF on \(T'\), implying that
On the other hand, by Proposition A, \(T'\) has a \(\gamma _{r2}(T')\)-function g such that \(2\in g(v_3)\). Then we can extend g on T by assigning \(\emptyset \) to \(v_2\) and \(\{1\}\) to \(v_1\), to obtain a 2RDF of weight \(\gamma _{r2}(T')+1\). Thus \(\gamma _{r2}(T')\ge \gamma _{r2}(T)-1\). It follows from (11) that \(\gamma _{r2}(T')= i_{r2}(T')\).
To show that this equality is strong, assume h is a \(\gamma _{r2}(T')\)-function that it is not independent. First let \(|h(v_3)|>0\). Assume without loss of generality that \(2\in h(v_3)\). Then the function \(h':V(T)\rightarrow {{\mathcal {P}}}(\{1,2\})\) defined by \(h'(v_1)=\{1\}, h'(v_2)=\emptyset \) and \(h'(x)=h(x)\) for \(x\in V(T)-\{v_1,v_2\}\) is a \(\gamma _{r2}(T)\)-function that is not independent, a contradiction. Let now \(|h(v_3)|=0\). Then \(|h(z_2)|+|h(z_1)|=2\). If \(\cup _{x\in N(v_3)-\{z_2\}}h(x)\ne \emptyset \), then we define \(g:V(T)\rightarrow {{\mathcal {P}}}(\{1,2\})\) by \(g(v_3)=\{1\}, g(z_2)=g(v_2)=\emptyset , g(z_1)=g(v_1)=\{2\}\) and \(g(x)=h(x)\) otherwise, to produce a \(\gamma _{r2}(T)\)-function that is not independent, a contradiction. Let \(\cup _{x\in N(v_3)-\{z_2\}}h(x)=\emptyset \). Then to rainbowly dominate \(v_3\), we must have \(h(z_2)=\{1,2\}\) and \(|h(z_1)|=0\). Then the function \(h_1:V(T')\rightarrow \mathcal {{\mathcal {P}}}(\{1,2\})\) defined by \(h_1(v_3)=\{1\}, h_1(z_2)=\emptyset , h_1(z_1)=\{2\}\), and \(h_1(x)=h(x)\) otherwise, is a \(\gamma _{r2}(T')\)-function that is not independent and \(|h_1(v_3)|>0\). This leads to a contradiction as above. Thus \(\gamma _{r2}(T')\equiv i_{r2}(T')\) and by inductive hypothesis we have \(T'\in {\mathcal {F}}\). Now T can be obtained from \(T'\) by Operation \({\mathcal {O}}_4\).
Subcase 2.2 \(\deg (v_3)=2\).
First let \(\deg (v_4)=2\). Let \(T'=T-\{v_1,v_2\}\). We show that \(\gamma _{r2}(T')\equiv i_{r2}(T')\). Let f be a \(\gamma _{r2}(T)\)-function such that \(f(v_1)=\{1\}\) and \(2\in f(v_3)\) (Proposition A). This implies that \(|f(v_2)|=0\). Since \(\gamma _{r2}(T)\equiv i_{r2}(T)\), f is an \(i_{r2}(T)\)-function. Obviously the function f, restricted to \(T'\), is an I2RDF on \(T'\), implying that
Now let g be a \(\gamma _{r2}(T')\)-function such that \(g(v_3)=\{1\}\) by Proposition A. We can extend g to a \(\gamma _{r2}(T)\)-function by assigning \(\emptyset \) to \(v_2\) and \(\{2\}\) to \(v_1\). This implies that \(\gamma _{r2}(T)\le \gamma _{r2}(T')+1\), and by (12) we obtain \(\gamma _{r2}(T')= i_{r2}(T')\).
Now we show that this equality is strong. Assume h is a \(\gamma _{r2}(T')\)-function that is not independent. If \(|h(v_3)|>0\), then we can extend h to a \(\gamma _{r2}(T)\)-function that is not independent by assigning \(\emptyset \) to \(v_2\) and \(\{1\}\) to \(v_1\) if \(2\in h(v_3)\) and \(\{2\}\) to \(v_1\) if \(1\in h(v_3)\), a contradiction with \(\gamma _{r2}(T)\equiv i_{r2}(T)\). Let \(|h(v_3)|=0\). Then to rainbowly dominate \(v_3\), we must have \(h(v_4)=\{1,2\}\). Since h is a \(\gamma _{r2}(T')\)-function and \(\deg (v_4)=2\), we must have \(|h(v_5)|=0\). Then the function \(h_1:V(T)\rightarrow {{\mathcal {P}}}(\{1,2\})\) defined by \(h_1(v_5)=h_1(v_1)=\{1\}, h_1(v_3)=\{2\}, h_1(v_2)=h_1(v_4)=\emptyset \) and \(h_1(x)=h(x)\) otherwise, is a \(\gamma _{r2}(T)\)-function which is not independent, a contradiction with \(\gamma _{r2}(T)\equiv i_{r2}(T)\). Hence \(\gamma _{r2}(T')\equiv i_{r2}(T')\) and by inductive hypothesis, \(T'\in {\mathcal {F}}\). Now T can be obtained from \(T'\) by Operation \({\mathcal {O}}_4\).
Next let \(\deg (v_4)\ge 3\). By Proposition A, T has a \(\gamma _{r2}\)-function f such that \(f(v_1)=\{1\}\), \(|f(v_2)|=0\) and \(2\in f(v_3)\). Also suppose among \(\gamma _{r2}(T)\)-functions with this property we choose a \(\gamma _{r2}(T)\)-function such that \(|f(v_4)|\) is as large as possible. If \(|f(v_3)|=2\), then the function \(g_1:V(T)\rightarrow {{\mathcal {P}}}(\{1,2\})\) defined by \(g_1(v_1)=\{1\}, g_1(v_2)=\emptyset , g_1(v_3)=\{2\}, g_1(v_4)=\{1\}\) and \(g_1(x)=f(x)\) for \(x\in V(T)-\{v_1,v_2,v_3,v_4\}\) is a \(\gamma _{r2}(T)\)-function that is not independent, a contradiction. Therefore \(|f(v_3)|=1\). Since \(\gamma _{r2}(T)\equiv i_{r2}(T)\), f is an I2RDF of T and hence \(f(v_4)=\emptyset \). This implies that neither \(v_4\) is a strong support vertex nor \(v_4\) has a support vertex of degree 2 in its neighborhood. If there is a path \(v_4y_3y_2y_1\) in \(T_4\) where \(y_3\ne v_3\) and \(\deg (y_1)=1\), then by the choice of diametral path \(v_1\ldots v_k\), we have \(|L_{v_2}|\ge |L_{y_2}|\) and \(|L_{v_3}|\ge |L_{y_3}|\) that implies \(\deg (y_2)=2\) and \(|L_{y_3}|=0\). Hence, if there is a leaf at distance three from \(v_4\) in \(T_{v_4}\), then it plays the same role of \(v_1\). Thus we may assume that each component of \(T_{v_4}-v_4\) is isomorphic to \(P_3\), \(K_{1, t}, (t\ge 2)\) or a single vertex, where \(v_4\) is adjacent to a leaf of each \(P_3\), the center of \(K_{1, t}\), or the single vertex, respectively.
Assume first that one of the components of \(T_{v_4}-v_4\) is \(K_{1, t}, (t\ge 2)\). That is, \(v_4\) has a strong support vertex such as z in its neighborhood. Let \(T'=T-\{v_1,v_2,v_3\}\) and let f be a \(\gamma _{r2}(T)\)-function. By Observation 2(a), we may assume \(f(z)=\{1,2\}\). Since \(\gamma _{r2}(T)\equiv i_{r2}(T)\), f is a \(i_{r2}(T)\)-function and hence \(|f(v_4)|=0\). Then clearly \(|f(v_1)|+|f(v_2)|+|f(v_3)|=2\) and \(f|_{V(T')}\) is an I2RDF on \(T'\), implying that
On the other hand, let \(f_1\) be a \(\gamma _{r2}(T')\)-function such that \(f_1(z)=\{1,2\}\) [Observation 2(a)]. We can extend \(f_1\) to a 2RDF on T with weight \(\gamma _{r2}(T')+2\) by assigning \(\{2\}\), \(\emptyset \) and \(\{1\}\) to \(v_3\), \(v_2\) and \(v_1\), respectively. Hence \(\gamma _{r2}(T)\le \gamma _{r2}(T')+2\) and by (13), we have \(\gamma _{r2}(T')= i_{r2}(T')\).
If there exists a \(\gamma _{r2}(T')\)-function h that is not independent, then as above we can extend h to a \(\gamma _{r2}(T)\)-function that is not independent, a contradiction with \(\gamma _{r2}(T)\equiv i_{r2}(T)\). Thus \(\gamma _{r2}(T')\equiv i_{r2}(T')\). It follows from inductive hypothesis that \(T'\in {\mathcal {F}}\) and so T can be obtained from \(T'\) by Operation \({\mathcal {O}}_5\).
Now suppose that \(v_4\) has no child which is a strong support vertex. We claim that \(|L_{v_4}|\le 1\). Let to the contrary that \(|L_{v_4}|\ge 2\). By Proposition A, T has a \(\gamma _{r2}\)-function f that \(f(v_1)=\{1\}\) and \(2\in f(v_3)\). Since \(|L_{v_4}|\ge 2\), we may assume \(f(v_4)=\{1,2\}\) which contradicts the assumption \(\gamma _{r2}(T)\equiv i_{r2}(T)\). Hence \(|L_{v_4}|\le 1\). Since \(\deg (v_4)\ge 3\), we deduce that \(T_{v_4}\in {{\mathcal {F}}}_2\). Let \(T'=T-T_{v_4}\) and let g be a \(\gamma _{r2}(T)\)-function with \(g(v_1)=\{1\}\) and \(2\in g(v_3)\). By assumption, g is an I2RDF of T and hence \(g(v_4)=\emptyset \). Then \(g|_{V(T')}\) is an I2RDF of \(T'\), implying that
where t is number of leaves adjacent to \(v_4\).
On the other hand, each \(\gamma _{r2}(T')\)-function f can be extended to a 2RDF of T by assigning \(\{2\}\) to \(v_3\), \(\{1\}\) to \(v_1\), each vertex of \(N(v_4){\setminus } (L_{v_4}\cup \{v_5,v_3\})\) and the leaf adjacent to \(v_4\), if any, \(\{2\}\) to every vertex in \(T_{v_4}\) at distance 3 from \(v_4\) except \(v_1\), and \(\emptyset \) to the other vertices of \(T_{v_4}\). It follows that \(\gamma _{r2}(T')\ge \gamma _{r2}(T)-2\deg (v_4)+2-t\). By (14) we obtain \(\gamma _{r2}(T')=i_{r2}(T')\).
If h is a \(\gamma _{r2}(T')\)-function that is not independent, then we can easily extend h to a \(\gamma _{r2}(T)\)-function that is not independent, a contradiction with \(\gamma _{r2}(T)\equiv i_{r2}(T)\). Thus \(\gamma _{r2}(T')\equiv i_{r2}(T')\). By inductive hypothesis, we have \(T'\in {\mathcal {F}}\). It can be easily seen that \(\gamma _{r2}(T'-v_5)\ge \gamma _{r2}(T')\) if \(v_4\) is a support vertex. Now T can be obtained from \(T'\) by Operation \({\mathcal {O}}_6\).
Case 3 \(|L_{v_3}|=1\).
Let w be the leaf adjacent to \(v_3\). We consider the following subcases.
Subcase 3.1 \(\deg (v_3)>3\).
Then \(v_3\) has a child \(z_2\ne v_2\) that is a support vertex of degree 2. Let \(z_1\) be the leaf adjacent to \(z_2\). Set \(T'=T-\{v_1,v_2\}\). We show that \(\gamma _{r2}(T')\equiv i_{r2}(T')\). Assume that f is a \(\gamma _{r2}(T)\)-function. We may assume that \(f(v_1)=\{1\}\) and \(2\in f(v_3)\) by Proposition A. Clearly \(|f(v_2)|=0\). Since \(\gamma _{r2}(T)\equiv i_{r2}(T)\), f is an I2RDF of T. Now \(f|_{V(T')}\) is an I2RDF of \(T'\) of weight \(\gamma _{r2}(T)-1\) which implies that
On the other hand, if \(f_1\) is a \(\gamma _{r2}(T')\)-function, then we may assume that \(2\in f_1(v_3)\) by Proposition A, and so \(f_1\) can be extended to a 2RDF of T of weight \(\gamma _{r2}(T')+1\) by assigning \(\emptyset \) to \(v_2\) and \(\{1\}\) to \(v_1\), implying that \(\gamma _{r2}(T)\le \gamma _{r2}(T')+1\). By (15) we obtain \(\gamma _{r2}(T')=i_{r2}(T')\).
To show that this equality is strong, suppose h is a \(\gamma _{r2}(T')\)-function which is not independent. We may assume \(|h(v_3)|>0\), for otherwise we must have \(|h(w)|=1\) and \(|h(z_2)|+|h(z_1)|=2\) and the function \(g:V(T')\rightarrow \mathcal P(\{1,2\})\) by \(g(v_3)=\{1\}\), \(g(z_2)=\emptyset , g(z_1)=g(w)=\{2\}\) and \(g(x)=h(x)\) otherwise, is a \(\gamma _{r2}(T')\)-function with the desired property. Then we can easily extend h to a \(\gamma _{r2}(T)\)-function that is not independent, a contradiction with \(\gamma _{r2}(T)\equiv i_{r2}(T)\). Thus \(\gamma _{r2}(T')\equiv i_{r2}(T')\) and by inductive hypothesis, \(T'\in {\mathcal {F}}\). Now T can be obtained from \(T'\) by Operation \({\mathcal {O}}_4\).
Subcase 3.2 \(\deg (v_3)=3\).
First let \(\deg (v_4)\ge 3\). Let f be a \(\gamma _{r2}(T)\)-function. By Corollary 1, we may assume \(f(v_3)=\{1, 2\}\). Since \(\gamma _{r2}(T)\equiv i_{r2}(T)\), f is an I2RDF of T. Then \(|f(v_4)|=0\) and \(|f(v_1)|=1\). If \(1\in \cup _{x\in N(v_4)-\{v_3\}} f(x)\) (the case \(2\in \cup _{x\in N(v_4)-\{v_3\}} f(x)\) is similar), then the function \(f_1:V(T)\rightarrow {{\mathcal {P}}}(\{1,2\})\) defined by \(f_1(v_1)=f_1(w)=\{1\}, f_1(v_3)=\{2\}, f_1(v_2)=\emptyset \) and \(f_1(x)=f(x)\) otherwise, is a \(\gamma _{r2}(T)\)-function which is not independent, a contradiction with \(\gamma _{r2}(T)\equiv i_{r2}(T)\). Thus \(|\cup _{x\in N[v_4]-\{v_3\}} f(x)|=0\). This implies that \(v_4\) has no child with depth 0 or 1. Assume that \(v_4\) has a child z with depth 2. Then any leaf of \(T_z\) at distance two from z plays the same role of \(v_1\), and thus by the previous arguments, we may assume that \(T_z\simeq T_{v_3}\) and as above we can define a \(\gamma _{r2}(T)\)-function g such that \(g(z)=g(v_3)=\{1,2\}\) which leads to a contradiction. Thus \(\deg (v_4)=2\). Suppose \(T'=T-T_{v_4}\). We show that \(i_{r2}(T')\equiv \gamma _{r2}(T')\). Let f be a \(\gamma _{r2}(T)\)-function that assigns \(\{1, 2\}\) to \(v_3\) and \(\emptyset \) to \(v_4\), according to Corollary 1. Note that f is also an I2RDF of T because \(i_{r2}(T)\equiv \gamma _{r2}(T)\). Then \(f|_{V(T')}\) is an I2RDF on \(T'\), implying that
On the other hand, every \(\gamma _{r2}(T')\)-function can be extended to a 2RDF of T by assigning \(\{1\}\) to \(v_1\), \(\emptyset \) to \(v_2,v_4,w\) and \(\{1, 2\}\) to \(v_3\), and thus \(\gamma _{r2}(T)\le \gamma _{r2}(T')+3\). It follows from (16) that \(\gamma _{r2}(T')= i_{r2}(T')\).
If there is a \(\gamma _{r2}(T')\)-function g that is not independent then as above, we can extend it to a \(\gamma _{r2}(T)\)-function that is not independent, a contradiction. Thus \(\gamma _{r2}(T')\equiv i_{r2}(T')\). By the inductive hypothesis, \(T'\in {\mathcal {F}}\) and T can be obtained from \(T'\) by Operation \({\mathcal {O}}_7\) and the proof is completed. \(\square \)
Now we are ready to state the main theorem of this paper.
Theorem 14
Let T be a tree. Then \(i_{r2}(T)\equiv \gamma _{r2}(T)\) if and only if \(T\in {{\mathcal {F}}}\cup \{K_1\}\).
References
Aram, H., Sheikholeslami, S.M., Volkmann, L.: On the total \(\{k\}\)-domination and \(\{k\}\)-domatic number of a graph. Bull. Malays. Math. Sci. Soc. (2) 36(1), 39–47 (2013)
Aram, H., Atapour, M., Sheikholeslami, S.M., Volkmann, L.: Signed \(k\)-domatic number of digraphs. Bull. Malays. Math. Sci. Soc. (2) 36(1), 143–150 (2013)
Brešar, B., Henning, M.A., Rall, D.F.: Rainbow domination in graphs. Taiwan. J. Math. 12, 213–225 (2008)
Brešar, B., Šumenjak, T.K.: On the 2-rainbow domination in graphs. Discrete Appl. Math. 155, 2394–2400 (2007)
Dehgardi, N., Sheikholeslami, S.M., Volkmann, L.: The rainbow domination subdivision numbers of graphs. Mat. Vesn. 67, 102–114 (2015)
Dehgardi, N., Sheikholeslami, S.M., Volkmann, L.: The \(k\)-rainbow bondage number of a graph. Discrete Appl. Math. 174, 133–139 (2014)
Falahat, M., Sheikholeslami, S.M., Volkmann, L.: New bounds on the rainbow domination subdivision number. Filomat 28, 615–622 (2014)
Haynes, T.W., Henning, M.A., Slater, P.J.: Strong equality of domination parameters in trees. Discrete Math. 260, 77–87 (2003)
Haynes, T.W., Henning, M.A., Slater, P.J.: Strong equality of upper domination and independence in trees. Util. Math. 59, 111–124 (2001)
Haynes, T.W., Slater, P.J.: Paired-domination in graphs. Networks 32, 199–206 (1998)
Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Marcel Dekker Inc, New York (1998)
Sheikholeslami, S.M., Volkmann, L.: The \(k\)-rainbow domatic number of a graph. Discuss. Math. Graph Theory 32, 129–140 (2012)
West, D.B.: Introduction to Graph Theory. Prentice-Hall Inc, Englewood Cliffs (2000)
Wu, Y., Yu, Q.: A characterization of graphs with equal domination number and vertex cover number. Bull. Malays. Math. Sci. Soc. (2) 35, 803–806 (2012)
Zhao, Y., Shan, E., Liang, Z., Gao, R.: A labeling algorithm for distance domination on block graphs. Bull. Malays. Math. Sci. Soc. (2) 37, 965–970 (2014)
Acknowledgments
The authors would like to thank anonymous referees for their remarks and suggestions that helped improve the manuscripts.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Xueliang Li.
Rights and permissions
About this article
Cite this article
Amjadi, J., Falahat, M., Sheikholeslami, S.M. et al. Strong Equality Between the 2-Rainbow Domination and Independent 2-Rainbow Domination Numbers in Trees. Bull. Malays. Math. Sci. Soc. 39 (Suppl 1), 205–218 (2016). https://doi.org/10.1007/s40840-015-0284-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40840-015-0284-0