Menu
In this paper, we introduce the concept of the generalized \(3\)-rainbow dominating function of a graph \(G\). This function assigns an arbitrary subset of three colors to each vertex of the graph with the condition that every vertex (including its neighbors) must have access to all three colors within its closed neighborhood. The minimum sum of assigned colors over all vertices of G is defined as the \(g_{3}\)-rainbow domination number, denoted by \(\gamma_{g3r}\). We present a linear-time algorithm to determine a minimum generalized 3-rainbow dominating set for several graph classes: trees, paths \((P_n)\), cycles \((C_n)\), stars (\(K_1,n)\), generalized Petersen graphs \((GP(n,2)\), GP \((n,3))\), and honeycomb networks \((HC(n))\).
Domination and its variations in graphs have been extensively studied [1, 2]. For a graph \(G=(V,E)\), a set \(S\) is a domination set if each vertex in \(V \setminus S\) is adjacent to a vertex in \(S\). The domination number \(\gamma(G)\) is the minimum cardinality of a dominating set of \(G\). We call a dominating set of cardinality \(\gamma(G)\) a \(\gamma(G)\)-set. For subsets \(S,T \subseteq V\), the set \(S\) is said to dominate \(T\) if every vertex in \(T\) is adjacent to a vertex in \(S\).
Domination describes situations where every unoccupied vertex requires a guard in its adjacent vertices. In such scenarios, only one type of guard is assumed. Consider a more complex scenario where there are multiple types of guards (let’s say \(k\) types), and each vertex that lacks a guard must have all types of guards in its adjacent vertices.
From a practical perspective, consider a workshop with \(5\) mechanics performing the same task, each requiring \(7\) different tools. Why should only a mechanic with no tools have access to all the tools in their adjacent vertices? Instead, this condition should apply to all mechanics. In other words, a mechanic with one, two, three, or any number of tools should have access to all \(7\) required tools around them. Therefore, we propose a modification to the definition in the following article: “All graph vertices must see all labels in their neighborhood.” This relaxation leads to the following definitions:
Let \(G\) be a graph and let \(f\) be a function assigning to each vertex a subset of colors selected from the set \(\{1,2,3\}\); that is, \(f:V(G) \rightarrow \mathcal{P}\{1,2,3\}\). If for every vertex \(v \in V(G)\) such that \(f(v)=\emptyset\), we have \(\bigcup_{u \in V(G)} f(u) = \{1,2,3\}\).
A type of domination in graphs: Consider a set of \(3\) colors assigned randomly to each vertex of a graph \(G\). If we require that every vertex with an empty set assigned to it must have all \(3\) colors in its neighborhood, then this is called the \(3\)-rainbow dominating function of a graph \(G\). The parameter \(\gamma_{3r}\), which is the minimum total number of colors selected over all vertices of \(G\), is called the \(3\)-rainbow domination number of \(G\).
Definition 1. Assume \(G\) is a graph and let \(f\) be a function that assigns to each vertex a set of colorful items selected from the set \(\{1, 2, 3\}\); that is, \(f: V(G) \rightarrow \mathcal{P}(\{1, 2, 3\})\). A function \(f\) is described as a generalized \(3\)-rainbow dominating function (\(g3rdf\)) of \(G\) if for each vertex \(v \in V(G)\), we have \(\bigcup_{u \in N[v]} f(u) = \{1, 2, 3\}\). Therefore, \(f\) is named a generalized \(3\)-rainbow dominating function (\(g3rdf\)) of \(G\). The weight \(\omega(f)\) of a function \(f\) is defined as \(\omega(f) = \sum_{v \in V(G)} |f(v)|\). Given a graph \(G\), the minimum weight of a \(g3rdf\) is called the generalized \(3\)-rainbow dominating number of \(G\), denoted by \(\gamma_{g3r}(G)\).
The following theorem is simple.
Theorem 1. Assume \(G\) is a graph. Then, \[\min\{ |G|, \gamma(G)\} \leq \gamma_{g3r} \leq 3\gamma(G) .\tag{1}\]
Lemma 1.
\(\gamma_{g3r}(k_n)=3\)z.
\(\gamma_{g3r}(k_{m,n})=6\).
\(\gamma_{g3r}(k_{1,n})=3\).
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 \(\emptyset\). 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 \(\emptyset\), then \(w(f)=6\).
For graphs \(k_{1,n}\) or star graphs, \(\gamma_{g3r}\) is \(w(f)=3\).
◻
Definition 2. A tree graph with \(n\) vertices having \(k\) pendant vertices of degree \(k+2\), and the initial and final vertices of the graph have degree \(k+1\), is denoted by \(F_k\).
Theorem 2. For the tree graphs \(F_k\), \(\gamma_{g3r}=3n\).
Lemma 2. For the paths \(p_i\), we have
for \(p_i\) if \(i=2,3\), then \(\gamma_{g3r} = 3\),
for \(p_i\) if \(i, n\in \mathbb{N}\) and \(3n+1 \leq i \leq 3(n+1)\), then \(\gamma_{g2r} = 3n+3\).
Lemma 3. For the cycles \(C_n\), we have
for \(C_i\) if \(i=2,3\), then \(\gamma_{g3r} = 3\),
for \(C_i\) if \(i, n\in \mathbb{N}\) and \(i = 3n\), then \(\gamma_{g3r} = 3n\),
for \(C_i\) if \(i, n\in \mathbb{N}\) and \(3n+1 \leq i \leq 3(n+1)\), then \(\gamma_{g3r} = 3n+3\).
Definition 3. Assume \(n \leq 3\) and \(k\) be initial natural numbers \(k<n\). The generalized Petersen \(GP(n,k)\) is defined as follows. Let \(C_n\), \(C'_n\) be two decompositions of length \(n\). Suppose the vertices of \(C_n\) are \(u_1, \dots, u_n\) and edges \(u_iu_{i+1}\) for \(i=1, \dots, n-1\) and \(u_nu_1\). Assume the vertices of \(C'_n\) are \(v_1, \dots, v_n\) and edges \(v_iv_{i+k}\) for \(i=1, \dots, n\), the sum \(i+k\) being derived modulo (\(mod\)). The graph \(GP(n,k)\) is obtained from \(i=1, \dots, n\). It’s clear that \(GP(n,k) = GP(n,n-k)\). The graph \(GP(5,2)\) or \(GP(5,3)\) is the famous Petersen graph.
Theorem 3. For graphs \(GP(n,2)\) with \((n,2)=1\), we have \[ \begin{equation} \gamma_{g3r} \leq \left\{ \begin{array}{ll} 6\left\lfloor \frac{n}{3} \right\rfloor, & \text{if } n \equiv 0 \pmod{3}; \\ 6\left(\left\lfloor \frac{n}{3} \right\rfloor + 1\right), & \text{if } n \equiv 2 \pmod{3}; \\ 6\left\lfloor \frac{n}{3} \right\rfloor + 3, & \text{if } n \equiv 1 \pmod{3}. \end{array} \right. \end{equation}\label{2}\tag{2}\]
Proof. We use the following partition of \(V(GP(n,2))\):
a) If \(n \equiv 0 \pmod{3}\), then \(n=3k\). We use the following algorithm to define the function \(f\) on \(GP(n,2)\) where \((n,2)=1\):
\(f(u_i)=\emptyset\) if \(i \not\equiv 0 \pmod{3}\) and \(f(u_i)=\{1,2,3\}\) if \(i \equiv 0 \pmod{3}\).
\(f(v_{3t})=\emptyset = 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\left\lfloor \frac{n}{3} \right\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\left\lfloor \frac{n}{3} \right\rfloor\). Therefore, \(\gamma_{g3r} \leq 3\left\lfloor \frac{n}{3} \right\rfloor + 3\left\lfloor \frac{n}{3} \right\rfloor = 6\left\lfloor \frac{n}{3} \right\rfloor\).
b) If \(n \equiv 2 \pmod{3}\), then we use the following algorithm to define the function \(f\) on \(GP(n,2)\) where \((n,2)=1\):
\(f(u_i)=\emptyset\) if \(i \neq n\) and \(i \not\equiv 0 \pmod{3}\), \(f(u_i)=\{1,2,3\}\) if \(i \equiv 0 \pmod{3}\), and \(f(u_n)=\{1,2,3\}\).
\(f(v_{3t})=\emptyset = 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\left\lfloor \frac{n}{3} \right\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\left\lfloor \frac{n}{3} \right\rfloor + 3\). Therefore, \(\gamma_{g3r}(GP(n,2)) \leq 3\left\lfloor \frac{n}{3} \right\rfloor + 3 + 3\left\lfloor \frac{n}{3} \right\rfloor + 3 = 6\left\lfloor \frac{n}{3} \right\rfloor + 6\).
c) If \(n \equiv 1 \pmod{3}\), then we use the following algorithm to define the function \(f\) on \(GP(n,2)\) where \((n,2)=1\):
\(f(u_i)=\emptyset\) if \(i \neq n\) and \(i \not\equiv 0 \pmod{3}\), and \(f(u_i)=\{1,2,3\}\) if \(i \equiv 0 \pmod{3}\).
\(f(v_{3t})=\emptyset = 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\left\lfloor \frac{n}{3} \right\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\left\lfloor \frac{n}{3} \right\rfloor + 3\). Therefore, \(\gamma_{g3r}(GP(n,2)) \leq 3\left\lfloor \frac{n}{3} \right\rfloor + 3 + 3\left\lfloor \frac{n}{3} \right\rfloor + 3 = 6\left(\left\lfloor \frac{n}{3} \right\rfloor + 1\right)\).
◻
Theorem 4. For graphs \(GP(n,3)\) where \((n,3)=1\), we have: \[\label{3}\tag{3} \gamma_{g3r} \leq \left\{ \begin{array}{ll} 6\left\lfloor \frac{n}{3} \right\rfloor + 3, & \text{if } n \equiv 1 \pmod{3}; \\ 6\left\lceil \frac{n}{3} \right\rceil, & \text{if } n \equiv 2 \pmod{3}. \end{array} \right.\]
Proof. We use the following partition of \(V(GP(n,3))\):
a) If \(n \equiv 1 \pmod{3}\), we use the following algorithm to define the function \(f\) on \(GP(n,3)\) where \((n,3)=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 \(\emptyset\). This results in \(\gamma_{g3r}\) for the outer circle equal to \(3\left\lfloor \frac{n}{3} \right\rfloor + 3\).
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 \(\emptyset\). This results in \(\gamma_{g3r}\) for the inner circle equal to \(\frac{3}{2}\left\lfloor \frac{n}{3} \right\rfloor\). Therefore, \(\gamma_{g3r}(GP(n,3)) \leq 3\left\lfloor \frac{n}{3} \right\rfloor + 3 + \frac{3}{2}\left\lfloor \frac{n}{3} \right\rfloor + \frac{3}{2}\left\lfloor \frac{n}{3} \right\rfloor = 6\left\lfloor \frac{n}{3} \right\rfloor + 3\).
b) If \(n \equiv 2 \pmod{3}\), we use the following algorithm to define the function \(f\) on \(GP(n,3)\) where \((n,3)=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 \(\emptyset\). This results in \(\gamma_{g3r}\) for the outer circle equal to \(6\left\lceil \frac{n}{3} \right\rceil\).
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 \(\emptyset\). This results in \(\gamma_{g3r}\) for the inner circle equal to \(\frac{3}{2}\left\lceil \frac{n}{3} \right\rceil\). Therefore, \(\gamma_{g3r}(GP(n,3)) \leq 3\left\lceil \frac{n}{3} \right\rceil + \frac{3}{2}\left\lceil \frac{n}{3} \right\rceil + \frac{3}{2}\left\lfloor \frac{n}{3} \right\rfloor = 6\left\lceil \frac{n}{3} \right\rceil\).
◻
Definition 4. The honeycomb structure \(HC(1)\) has six sides. The honeycomb \(HC(2)\) is formed by appending six hexagons to the outer edges of \(HC(1)\). Similarly, the honeycomb system \(HC(n)\) is obtained from \(HC(n-1)\) by adding six sides around the perimeter of \(HC(1)\). The number of vertices and edges in \(HC(n)\) are \(6n^2\) and \(9n^2-3n\), respectively. In graph theory, the honeycomb system can be represented as a brick structure by collapsing one set of opposite vertices along the direct lines, resulting in the same number of vertices and edges. The honeycomb structure is widely used in various applications such as all-to-all broadcasting in computer networking and in chemistry to model the shape of various compounds.
Lemma 4. [3] The boundary of \(HC(n)\) is the cycle \(C_{6(2n-1)}\).
Lemma 5. [3] For \(n \geq 2\), \(\vert V(HC(n)) \vert – \vert V(HC(n-1)) \vert = 6(2n-1)\).
Theorem 5. For the honeycomb network \(HC(n)\), we have \[\gamma_{g3r} HC(n) = \sum_{k=2}^{n} \gamma_{g3r} C_{3(4k-2)} = \sum_{k=2}^{n} 3(4k-2).\]
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 \(\emptyset\), 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\}, \emptyset, \emptyset, \{1,2,3\}, \emptyset, \emptyset, \dots, \emptyset.\]
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).\]
Remark 1. The generalized \(3\)-rainbow dominating number of the honeycomb network \(HC(n)\) is equal to the generalized \(3\)-rainbow dominating number of the same cycle and the previous cycles.
Then, \[\begin{aligned} \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{aligned}\]
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).\] ◻
In this paper, we have extended the concept of \(3\)-rainbow domination to make it more applicable in various fields while reducing associated costs. Instead of requiring vertices with empty labels, we introduced a new condition that each vertex must have \(3\) neighbors. This generalized \(3\)-rainbow domination was applied to simple graphs as well as honeycomb networks.
Moving forward, there are several avenues for future research. One potential direction is to extend the concept of generalized \(k\)-rainbow domination to honeycomb networks and develop different algorithms to solve related problems.
The authors declare no conflict of interest.