Generalized 3-Rainbow Domination in Graphs and Honeycomb System (HC(n))

Proof.

• To check ${\gamma }_{g3r}$ for graphs $k_n$, where $V(k_n)=\{v_1,\dots ,v_n\}$, we can label $f(v_1)=\{1,2,3\}$ and the rest of the vertices as $\mathrm{\varnothing }$. Then, ${\gamma }_{g3r}=3$ and $\gamma (G)=1$.

• Generally, for graphs $k_{m,n}$, where $V(k_{m,n})=\{u_1,\dots ,u_m,v_1,\dots ,v_n\}$ with $u_i$ not adjacent to $v_j$ and vice versa, we can label $f(u_1)=\{1\}$, $f(u_2)=\{2\}$, $f(v_1)=\{1\}$, and $f(v_2)=\{2\}$. Since $f(u_1)=\{1\}$ and $f(v_1)=\{1\}$, and $f(v_2)=\{2\}$, at least one of the remaining vertices must have $f=\{3\}$, say $f(v_3)=\{2\}$, and then for the same reason, $f(u_3)=\{3\}$. Therefore, if the rest of the vertices are $\mathrm{\varnothing }$, then $w(f)=6$.

• For graphs $k_{1,n}$ or star graphs, ${\gamma }_{g3r}$ is $w(f)=3$.

Proof. We use the following partition of $V(GP(n,2))$:

a) If $n\equiv 0(\mathrm{mod}3)$, then $n=3k$. We use the following algorithm to define the function $f$ on $GP(n,2)$ where $(n,2)=1$:

1. $f(u_i)=\mathrm{\varnothing }$ if $i\not\equiv 0(\mathrm{mod}3)$ and $f(u_i)=\{1,2,3\}$ if $i\equiv 0(\mathrm{mod}3)$.

2. $f(v_{3t})=\mathrm{\varnothing }=f(v_{3t-1})$ for $t=1,2,\dots$, $f(v_{3t+1})=\{1,2,3\}$ for $t=0,1,2,\dots$.

In the graph $GP(n,2)$, the outer circle consists of vertices with multiples of $3$ labeled $\{1,2,3\}$, resulting in ${\gamma }_{g3r}$ for the outer circle equal to $2\lfloor \frac{n}{3}\rfloor$, and the inner circle consists of vertices with multiples of $3k+1$ labeled $\{1,2,3\}$, resulting in ${\gamma }_{g3r}$ for the inner circle equal to $3\lfloor \frac{n}{3}\rfloor$. Therefore, ${\gamma }_{g3r}\le 3\lfloor \frac{n}{3}\rfloor +3\lfloor \frac{n}{3}\rfloor =6\lfloor \frac{n}{3}\rfloor$.

b) If $n\equiv 2(\mathrm{mod}3)$, then we use the following algorithm to define the function $f$ on $GP(n,2)$ where $(n,2)=1$:

1. $f(u_i)=\mathrm{\varnothing }$ if $i\ne n$ and $i\not\equiv 0(\mathrm{mod}3)$, $f(u_i)=\{1,2,3\}$ if $i\equiv 0(\mathrm{mod}3)$, and $f(u_n)=\{1,2,3\}$.

2. $f(v_{3t})=\mathrm{\varnothing }=f(v_{3t-1})$ for $t=0,1,2,\dots$, $f(v_{3t+1})=\{1,2,3\}$ for $t=1,2,\dots$.

In the graph $GP(n,2)$, the outer circle consists of vertices with multiples of $3$ and the vertex $u_n$ labeled $\{1,2,3\}$, resulting in ${\gamma }_{g3r}$ for the outer circle equal to $3\lfloor \frac{n}{3}\rfloor +3$, and the inner circle consists of vertices with multiples of $3k+1$ labeled $\{1,2,3\}$, resulting in ${\gamma }_{g3r}$ for the inner circle equal to $3\lfloor \frac{n}{3}\rfloor +3$. Therefore, ${\gamma }_{g3r}(GP(n,2))\le 3\lfloor \frac{n}{3}\rfloor +3+3\lfloor \frac{n}{3}\rfloor +3=6\lfloor \frac{n}{3}\rfloor +6$.

c) If $n\equiv 1(\mathrm{mod}3)$, then we use the following algorithm to define the function $f$ on $GP(n,2)$ where $(n,2)=1$:

1. $f(u_i)=\mathrm{\varnothing }$ if $i\ne n$ and $i\not\equiv 0(\mathrm{mod}3)$, and $f(u_i)=\{1,2,3\}$ if $i\equiv 0(\mathrm{mod}3)$.

2. $f(v_{3t})=\mathrm{\varnothing }=f(v_{3t-1})$ for $t=1,2,\dots$, $f(v_{3t+1})=\{1,2,3\}=f(v_n)$ for $t=0,1,2,\dots$.

In the graph $GP(n,2)$, the outer circle consists of vertices with multiples of $3$ and the vertex $u_n$ labeled $\{1,2,3\}$, resulting in ${\gamma }_{g3r}$ for the outer circle equal to $3\lfloor \frac{n}{3}\rfloor +3$, and the inner circle consists of vertices with multiples of $3k+1$ and the vertex $v_n$ labeled $\{1,2,3\}$, resulting in ${\gamma }_{g3r}$ for the inner circle equal to $3\lfloor \frac{n}{3}\rfloor +3$. Therefore, ${\gamma }_{g3r}(GP(n,2))\le 3\lfloor \frac{n}{3}\rfloor +3+3\lfloor \frac{n}{3}\rfloor +3=6(\lfloor \frac{n}{3}\rfloor +1)$.

Proof. We use the following partition of $V(GP(n,3))$:

a) If $n\equiv 1(\mathrm{mod}3)$, we use the following algorithm to define the function $f$ on $GP(n,3)$ where $(n,3)=1$:

1. In the graph $GP(n,3)$, the vertices $u_{3k+1}$ for $k=0,1,2,\dots$ in the outer circle are labeled $\{1,2,3\}$, and the rest of the vertices are labeled $\mathrm{\varnothing }$. This results in ${\gamma }_{g3r}$ for the outer circle equal to $3\lfloor \frac{n}{3}\rfloor +3$.

2. Vertices $v_{3k+2}$ for $k=0,2,4,\dots$ in the inner circle are labeled $\{1,2,3\}$, and vertices $v_{3k}$ for $k=1,3,5,\dots$ are also labeled $\{1,2,3\}$. The rest of the vertices are labeled $\mathrm{\varnothing }$. This results in ${\gamma }_{g3r}$ for the inner circle equal to $\frac{3}{2}\lfloor \frac{n}{3}\rfloor$. Therefore, ${\gamma }_{g3r}(GP(n,3))\le 3\lfloor \frac{n}{3}\rfloor +3+\frac{3}{2}\lfloor \frac{n}{3}\rfloor +\frac{3}{2}\lfloor \frac{n}{3}\rfloor =6\lfloor \frac{n}{3}\rfloor +3$.

b) If $n\equiv 2(\mathrm{mod}3)$, we use the following algorithm to define the function $f$ on $GP(n,3)$ where $(n,3)=1$:

1. In the graph $GP(n,3)$, the vertices $u_{3k+1}$ for $k=0,1,2,\dots$ in the outer circle are labeled $\{1,2,3\}$, and the rest of the vertices are labeled $\mathrm{\varnothing }$. This results in ${\gamma }_{g3r}$ for the outer circle equal to $6\lceil \frac{n}{3}\rceil$.

2. Vertices $v_{3k+2}$ for $k=0,2,4,\dots$ in the inner circle are labeled $\{1,2,3\}$, and vertices $v_{3k}$ for $k=1,3,5,\dots$ are also labeled $\{1,2,3\}$. The rest of the vertices are labeled $\mathrm{\varnothing }$. This results in ${\gamma }_{g3r}$ for the inner circle equal to $\frac{3}{2}\lceil \frac{n}{3}\rceil$. Therefore, ${\gamma }_{g3r}(GP(n,3))\le 3\lceil \frac{n}{3}\rceil +\frac{3}{2}\lceil \frac{n}{3}\rceil +\frac{3}{2}\lfloor \frac{n}{3}\rfloor =6\lceil \frac{n}{3}\rceil$.

Proof. According to Lemma 1, $HC(1)=C_6$ and $HC(2)=C_{18}$, and so on, where $HC(n)=C_{6(2n-1)}$. To find the generalized $3$-rainbow dominating number of the honeycomb network $HC(n)$, we label each cycle separately up to the $n$th cycle. Then, we calculate ${\gamma }_{g3r}$ for each cycle and add them together. The labeling algorithm starts by labeling all the vertices of the first cycle with $\mathrm{\varnothing }$, so ${\gamma }_{g3r}HC(1)=0$.

To label the second cycle (without considering subsequent cycles), we select an arbitrary vertex with degree $3$ and label it $\{1,2,3\}$, and then label the rest of the vertices in the cycle in the same pattern as the first cycle. The vertices are labeled as follows: $$\{1,2,3\},\mathrm{\varnothing },\mathrm{\varnothing },\{1,2,3\},\mathrm{\varnothing },\mathrm{\varnothing },\dots ,\mathrm{\varnothing }.$$

According to Lemma 3, ${\gamma }_{g3r}{C}_{3n}=3n$. So, for $k$ being the number of cycles, $${\gamma }_{g3r}HC(2)={\gamma }_{g3r}{C}_{6(2(2)-1)}={\gamma }_{g3r}{C}_{18}={\gamma }_{g3r}{C}_{3(6)}=3(4k-2).$$

Then, $$\begin{array}{rl}{\gamma }_{g3r}HC(3)& ={\gamma }_{g2r}{C}_{6(2(3)-1)}+{\gamma }_{g3r}{C}_{6(2(2)-1)}\\ & ={\gamma }_{g3r}{C}_{30}+{\gamma }_{g2r}{C}_{18}\\ & =\sum _{k=2}^3{\gamma }_{g3r}{C}_{3(4k-2)}\\ & =\sum _{k=2}^{3}3(4k-2).\end{array}$$

This process continues until $${\gamma }_{g3r}HC(n)=\sum _{k=2}^n{\gamma }_{g3r}{C}_{3(4k-2)}=\sum _{k=2}^{n}3(4k-2).$$