Dominator coloring is a fascinating type of proper coloring where vertices are assigned colors so that every vertex in the graph is within the closed neighborhood of at least one vertex from each color class. The smallest number of colors needed for a dominator coloring is called the dominator chromatic number. In this paper, a new graph product called the closed extended neighborhood corona of two graphs is introduced and its dominator chromatic number for any pair of connected graphs is determined. Also, the dominator chromatic numbers for the extended corona of a path with any graph and a cycle with any graph are derived. Additionally, the dominator chromatic number for the closed neighborhood corona of any two graphs is established.
An ordered triple defined as \(G = \{V(G), E(G), I_G\}\) is referred to as a graph [3, 13]. We focus on simple, finite graphs that are undirected and connected. The set of vertices and edges in the graph \(G\) is denoted by \(V(G)\) and \(E(G)\), respectively. The closed neighborhood \(N_G(v)\) of a vertex \(v\) includes \(v\) along with all its adjacent vertices. A subset \(S\) of the vertex set \(V(G)\) is called a dominating set for the graph \(G\) if every vertex in the complement set \(V(G) – S\) is adjacent to at least one vertex in \(S\). In this context, we say that \(S\) serves as a dominator for the vertices in \(V(G) – S\). The domination number \(\gamma(G)\) is defined as the minimum size of a dominating set within the graph \(G\). This paper primarily focuses on the path and cycle graphs, denoted by \(P_n\) and \(C_n\), respectively, where \(n\) indicates the number of vertices.
The use of graph coloring has a rich history across various applications. A proper coloring is defined as an assignment of colors \(\{c_1, c_2, \ldots\}\) to the vertices of a graph such that no two adjacent vertices share the same color \(c_i\). Each group of vertices that share a color forms a distinct color class and the minimum number of colors required for a proper coloring is called the chromatic number \(\chi(G)\). One notable coloring technique is the Dominator coloring.
Gera et al. introduced this coloring method in [11], drawing inspiration from the work of Hedetniemi et al. in [7, 8]. Arumugam et al. explored the algorithmic aspects of dominator coloring in [2], while Chellali provided a polynomial-time computation for the dominator chromatic number of certain graphs in [4]. However, it is known that determining the dominator chromatic number is NP-complete. The concept of the corona product of graphs was first defined by R. Frucht and F. Harary in 1970 [9] and since then, various researchers have investigated different variants of the corona product such as in [1, 12]. The dominator chromatic number for the cartesian products of \(P_2\) and \(P_3\) with arbitrary paths and cycles was established in [5, 6]. Additionally, several cartesian products, direct products and some corona products were examined in [15] and the dominator coloring of the corona of any two connected graphs was addressed in [14]. The concept of the closed neighborhood corona of graphs was introduced by Bishal Sonar and Ravi Srivastava in [16].
This research paper presents a novel concept known as the closed extended neighborhood corona of two graphs and establishes the precise values of its dominator chromatic number for any pair of connected graphs. Additionally, it explores the dominator chromatic number for the extended corona product of a path with any graph, a cycle with any graph and the closed neighborhood corona of any two connected graphs.
Basic definitions and results regarding the coloring are referred from [4, 10, 11].
Definition 2.1. [11] A Dominator coloring of a graph \(G\) is a proper coloring in which every vertex is adjacent to all the vertices of atleast one color class. The least number of colors required for the Dominator coloring is called as the Dominator chromatic number, denoted by \(\chi_d(G)\).
Definition 2.2. [9] The corona \(G_1 \circ G_2\) of any two graphs \(G_1\) and \(G_2\) is a graph obtained by taking one copy of \(G_1\) and \(|V(G_1)|\) copies of \(G_2\) and then joining the \(s^{th}\) vertex of \(G_1\) to every vertex in the \(s^{th}\) copy of \(G_2\).
Definition 2.3. [1] The extended corona \(G_1 \bullet G_2\) of any two graphs \(G_1\) and \(G_2\) is a graph obtained by taking the corona \(G_1 \circ G_2\) and joining each vertex of the \(s^{th}\) copy of \(G_2\) to every vertex of the \(t^{th}\) copy of \(G_2\), provided the vertices \(v_s\) and \(v_t\) are adjacent in \(G_1\).
Definition 2.4. [12] The neighborhood corona \(G_1 \star G_2\) of two graphs \(G_1\) and \(G_2\) is the graph obtained by taking one copy of \(G_1\) and \(|V(G_1)|\) copies of \(G_2\) and joining every neighbour of the \(s^{th}\) vertex of \(G_1\) to every vertex in the \(s^{th}\) copy of \(G_2\).
Definition 2.5. [1] The extended neighborhood corona \(G_1 \ast G_2\) of two graphs \(G_1\) and \(G_2\) is a graph obtained by taking the neighborhood corona \(G_1 \star G_2\) and joining each vertex of the \(s^{th}\) copy of \(G_2\) to every vertex of the \(t^{th}\) copy of \(G_2\), provided the vertices \(v_s\) and \(v_t\) are adjacent in \(G_1\).
Lemma 2.6. [10] Let G be a connected graph. Then, \[max\{\chi{(G)},\gamma(G)\}\leq \chi_d(G)\leq \chi{(G)}+\gamma(G).\]
Proposition 2.7. [11] For the path \({P}_{n},\) \[\chi_d({P}_n)=\begin{cases} \lceil{\frac{n}{3}}\rceil+1, \quad\quad\quad \ \ if \ n=2,3,4,5,7,\\ \lceil{\frac{n}{3}}\rceil+2, \quad\quad\quad \ \ otherwise. \end{cases}\]
Proposition 2.8. [10] The dominator chromatic number of the cycle \(C_{n}\) is, \[\chi_d(C_{n}) = \begin{cases} \lceil{\frac{n}{3}}\rceil, \quad\quad\quad \ \ if \ n \ = \ 4,\\ \lceil{\frac{n}{3}}\rceil+1, \quad\quad if \ n \ = \ 5,\\ \lceil{\frac{n}{3}}\rceil+2, \quad\quad otherwise. \end{cases}\]
In this section, the dominator chromatic number of the extended corona product of a path with any graph and a cycle with any graph is calculated.
Theorem 3.1. The dominator chromatic number of the extended corona of the path \(P_n\) with any connected graph \(G\) is, \[\chi_{d}(P_n \bullet G)= 2 \chi_d(P_n)+2\chi(G)-k,\] where \(\begin{cases} k=3 \ when \ n=3,4,5,7,\\ k=5 \ when \ n\equiv 1(mod \ 3), n\geq 10,\\ k=4 \ otherwise. \end{cases}\)
Proof. Consider a path \(P_n\) with \(n\) vertices and let \(G\) denote any connected graph consisting of \(m\) vertices. Define the vertex sets as \(V(P_n)=\{a_s:1\leq s \leq n\}\) and \(V(G)=\{b_t:1\leq t \leq m\}\). For each \(s\), associate a copy of \(G\), denoted as \(G^s\), with the vertices labeled \(V(G^s)=\{b_t^s : 1\leq s \leq n, 1\leq t \leq m\}\). Consequently, the vertex set for the product graph is given by \(V(P_n \bullet G) = V(P_n) \cup V(G^s)\), resulting in a total vertex count of \(n(m+1)\).
Define a function \(\varphi : V(P_n \bullet G) \rightarrow \{1,2,\cdots, \chi_{d}(P_n \bullet G)\}\). Begin by coloring the vertices of the path \(P_n\) using its dominator coloring as described in [11] such that \(\varphi(a_s)=\{1,2,\cdots,\chi_d(P_n)\}\). The following part of the theorem is divided into two cases accordingly. The coloring transformation is specified according to the values of \(s\) and \(t\).
Case i. When n = 3,4,5,7.
There are two scenarios to consider to specifically apply the coloring transformation in this case.
\(\bullet\) When s is odd and for \(1\leq t \leq m\): \[\varphi(b_t^s) = \{ \chi_d(P_n)+1, \chi_d(P_n)+2, \cdots, \chi_d(P_n)+\chi(G)\}.\]
\(\bullet\) When s is even and for \(1\leq t \leq m\): \[\begin{aligned} \varphi(b_t^s) =& \{ 1\} \cup \left\{\chi_d(P_n)+\chi(G)+1, \chi_d(P_n)+\chi(G)+2, \cdots, \chi_d(P_n)+2\chi(G)-2\right\} \ \\ &\cup \left\{\chi_d(P_n)+2\chi(G)-2+\frac{s}{2}\right\}. \end{aligned}\]
In each scenario, we properly utilize the colors from the given set for every copy. It’s important to use the last set in the union, specifically when \(s\) is even, as it corresponds to a unique color for each copy. The second set in the union may or may not be needed, depending on the structure of the graph and its proper coloring. Since \(P_n\) is assigned a dominator coloring, the unique coloring sequence of vertices is similarly applied to their respective copies, ensuring that all vertices in the product graph dominate at least one color class, denoted as \(\phi_i\). This way of dominator coloring results in a total of \(2 \chi_d(P_n)+2\chi(G)-3\) colors proving that \(\chi_{d}(P_n \bullet G) \leq 2 \chi_d(P_n)+2\chi(G)-3\).
It remains to show that \(\chi_{d}(P_n \bullet G) \geq 2 \chi_d(P_n)+2\chi(G)-3.\)
When \(n=3,4,5,7\), the dominator coloring of path \(P_n\) utilizes \(\lceil{\frac{n}{3}}\rceil+1\) colors, with a unique color assigned to each pair of alternating vertices. Hence, in addition to the dominator coloring of \(P_n\), a distinct color should be used for every \(s^{th}\) copy of \(G\), when \(s\) is even.
For every \(s\), a proper coloring of the vertex copies is necessary and sufficient.
If fewer than this number of colors is used, at least one vertex will fail to dominate any color class, including its own. Thus, to ensure dominance, we need at least \(2 \chi_d(P_n)+2\chi(G)-3\) colors. Therefore, \(\chi_{d}(P_n \bullet G)\geq 2 \chi_d(P_n)+2\chi(G)-3.\)
An example of this case is provided in the Figure 1 that depicts the extended corona product of the path \(P_3\) with \(P_3\).
Now, for the second and third cases specified in the theorem statement, the following transformation is applicable to both.
Case ii. When n \(\equiv\) 1(mod 3), n \(\geq\) 10 and otherwise.
In this case also, there are three particular scenarios to consider while applying the transformation.
\(\bullet\) When s is odd and for \(1\leq t \leq m\): \[\varphi(b_t^s) = \{2\} \cup \{ \chi_d(P_n)+1, \chi_d(P_n)+2, \cdots, \chi_d(P_n)+\chi(G)-1\} .\]
\(\bullet\) When s is even and for \(1\leq t \leq m\): \[\varphi(b_t^s) = \{ 1\} \cup \{\chi_d(P_n)+\chi(G), \chi_d(P_n)+\chi(G)+1, \cdots, \chi_d(P_n)+2\chi(G)-2\}.\]
\(\bullet\) When \(s\equiv 2 (mod \ 3)\) and for atleast one value of t: \[\varphi(b_t^s) = \chi_d(P_n)+2\chi(G)-2+\lceil{\frac{s}{3}}\rceil.\]
In the last scenario, the value of \(t\) is selected based on the graph structure and its proper coloring. However, when \(s \equiv 2 \ ( mod \ 3)\), it becomes necessary to color at least one vertex with a distinct color. In each case, we effectively utilize the colors from the given set for every copy.
As previously stated, each copy adopts the dominator coloring of \(P_n\), so every vertex dominates a color class, \(\phi_i\). This method of dominator coloring leads to a total of \(2 \chi_d(P_n) + 2 \chi(G) – k\) colors, which demonstrates that \(\chi_d(P_n \bullet G) \leq 2 \chi_d(P_n) + 2 \chi(G) – k\). The value of \(k\) varies depending on the value of \(n\), as outlined in the theorem statement.
It remains to establish that \(\chi_d(P_n \bullet G) \geq 2 \chi_d(P_n) + 2 \chi(G) – k\).
When \(n\equiv 1(mod \ 3), n\geq 10\), the dominator coloring of the path \(P_n\) is implemented such that the \(n^{th}\) vertex is assigned a unique color. The remaining \(n-1\) vertices are organized into groups of three, where each group dominates the central vertex. The graph copy of the \(n^{th}\) vertex does not require a distinct color for dominance. Hence, in addition to the dominator coloring of \(P_n\), it is both necessary and sufficient to use a unique color for every \(s^{th}\) copy of \(G\), when \(s\equiv 2(mod \ 3 )\).
On the contrary, when \(n\not\equiv 1(mod \ 3), n\geq 10\), the dominator coloring of the path \(P_n\) assigns a unique color to every \(s^{th}\) vertex, when \(s \equiv 2(mod \ 3)\). Hence, similar to the previous scenario, in addition to the dominator coloring of \(P_n\), a unique color must also be applied to every \(s^{th}\) copy of \(G\), when \(s\equiv 2(mod \ 3)\). The only difference is that the total number of unique colors needed in this case is one more than what is required when \(n \equiv 1 \ (\text{mod} \ 3)\).
Also, for every \(s\), an appropriate coloring of the vertex copies is necessary. If we use fewer colors than this number, at least one vertex will fail to dominate any color class, including its own. Therefore, to ensure dominance, we need at least \(2 \chi_d(P_n)+2\chi(G)-k\) colors to achieve dominance. Thus, \(\chi_{d}(P_n \bullet G)\geq 2 \chi_d(P_n)+2\chi(G)-k,\) where \(k=5\) when \(n\equiv 1(mod \ 3)\) and \(k=4\) otherwise. ◻
Theorem 3.2. The dominator chromatic number of the extended corona of the cycle \(C_n\) with any connected graph \(G\) is \[\chi_{d}(C_n \bullet G)= \begin{cases} \chi_d(C_n)+3\chi(G)-3 \quad \quad \ when \ n=3\\ \chi_d(C_n)+2\chi(G) \quad \quad \quad \quad when \ n=4\\ 2 \chi_d(C_n)+3\chi(G)-k \ \ \ \begin{cases} k=4 \ when \ n=5\\ k=5 \ when \ n \equiv 1(mod \ 2) \ , n\geq 7 \end{cases}\\ 2 \chi_d(C_n)+2\chi(G)-k \ \ \ \begin{cases} k=5 \ when \ n\equiv 1 (mod \ 3), n \ is \ even\\ k=4 \ otherwise. \end{cases} \end{cases}\]
Proof. Consider a cycle \(C_n\) with \(n\) vertices and let \(G\) denote any connected graph consisting of \(m\) vertices. Similar to the previous consideration, define the vertex sets as \(V(C_n)=\{a_s:1\leq s \leq n\}\) and \(V(G)=\{b_t:1\leq t \leq m\}\). For each \(s\), associate a copy of \(G\), denoted as \(G^s\), with vertices labeled \(V(G^s)=\{b_t^s : 1\leq s \leq n, 1\leq t \leq m\}\). Consequently, the vertex set for the product graph is given by \(V(C_n \bullet G) = V(C_n) \cup V(G^s)\), resulting in a total vertex count of \(n(m+1)\).
Define a function \(\varphi : V(C_n \bullet G) \rightarrow \{1,2,\cdots, \chi_{d}(C_n \bullet G)\}\). Begin by coloring the vertices of the cycle \(C_n\) using its dominator coloring as outlined in [10] such that \(\varphi(a_s)=\{1,2,\cdots,\chi_d(C_n)\}\). The subsequent part of the theorem is divided into four cases based on the values of \(s\) and \(t\).
Case i. When n = 3
Consider applying the mapping for three particular conditions as follows:
\(\bullet\) When s=1 and for \(1\leq t \leq m\): \[\varphi(b_t^s) = \{ 2,3, \cdots, \chi(G)+1\} .\]
\(\bullet\) When s=3 and for \(1\leq t \leq m\): \[\varphi(b_t^s) = \{\chi(G)+2, \chi(G)+3, \cdots, 2\chi(G)+1\}.\]
\(\bullet\) When s=2 and for \(1\leq t \leq m\): \[\varphi(b_t^s) = \{1\} \cup \{2\chi(G)+2,2\chi(G)+3, \cdots, \chi_d(C_n)+3\chi(G)-3 \}.\]
This method of dominator coloring ensures that every vertex in the product graph dominates at least one color class, whether it constitutes the vertices \(a_s\) or their copies. Consequently, we can conclude that \(\chi_{d}(C_n \bullet G) \leq \chi_d(C_n) + 3\chi(G) – 3\).
To establish the lower bound, consider a proper coloring of the graph \(C_3 \bullet G\), which yields \(\chi(C_3 \bullet G) = \chi(C_n) + 3\chi(G) – 3\). Upon verification, it becomes evident that a proper coloring of the graph is sufficient to achieve dominance in this scenario. Therefore, according to Lemma 2.6, we can confirm that \(\chi_{d}(C_n \bullet G) \geq \chi_d(C_n) + 3\chi(G) – 3\).
Case ii. When n = 4
Consider the following transformation:
\(\bullet\) When s=1,3 and for \(1\leq t \leq m\): \[\varphi(b_t^s) = \{ 3,4, \cdots, \chi(G)+2\}.\]
\(\bullet\) When s=2,4 and for \(1\leq t \leq m\): \[\varphi(b_t^s) = \{\chi(G)+3, \chi(G)+4, \cdots, 2\chi(G)+2\}.\]
In this context, the vertices \(a_s\) maintain their typical dominance in \(C_4\). Additionally, the vertex copies establish dominance in such a way that the odd copies dominate the even ones and vice versa. Thus, \(\chi_{d}(C_n \bullet G) \leq \chi_d(C_n)+2\chi(G).\)
It remains to prove the lower bound.
Since the vertices \(a_s\) are assigned their dominator coloring, it is not possible to reuse those colors for any vertex in the copies. Therefore, we need at least \(\chi(G)\) colors beyond \(\chi_d(G)\) to ensure dominance.
Furthermore, considering the structure, we require distinct colors for each odd and even copy. Thus, \(\chi_{d}(C_n \bullet G) \geq \chi_d(C_n)+2\chi(G).\)
Case iii. When n \(\equiv\) 1(mod 2)
This case is considered to prove the following sub-cases.
Subcase i. Consider the following transformation when n = 5:
\(\bullet\) When s=1 and for \(1\leq t \leq m\): \[\varphi(b_t^s) = \{3\} \cup \{ 4,5, \cdots, \chi(G)+2\}.\]
\(\bullet\) When s=3 and for \(1\leq t \leq m\): \[\varphi(b_t^s) = \{2\} \cup \{4,5, \cdots, \chi(G)+2\}.\]
\(\bullet\) When s=5 and for \(1\leq t \leq m\): \[\varphi(b_t^s) = \{\chi(G)+3,\chi(G)+4, \cdots, 2\chi(G)+2 \}.\]
\(\bullet\) When s=2,4 and for \(1\leq t \leq m\): \[\varphi(b_t^s) = \{1\} \cup \{2\chi(G)+3,2\chi(G)+4, \cdots, 3\chi(G) \} \cup \left\{3\chi(G)+\frac{s}{2}\right\}.\]
This method of dominator coloring ensures that every vertex in the product graph dominates at least one color class, whether associated with the vertices \(a_s\) or their copies. Therefore, we conclude that \(\chi_{d}(C_n \bullet G) \leq 2 \chi_d(C_n) + 3\chi(G) – 4\).
Next, we need to establish the lower bound.
In \(C_5\), the vertex \(a_1\) relies on \(a_5\) for dominance, while the vertex \(a_3\) depends on \(a_2\) and \(a_4\). Therefore, it is possible to reassign the colors accordingly. A careful analysis indicates that we can use the colors assigned to vertices \(a_5\), \(a_2\), and \(a_4\) for the first and third copies, respectively.
Since the first copy is fully connected to the \(n^{th}\) copy, at least \(\chi(G)\) distinct colors are needed for the last copy.
Additionally, two distinct colors are required for the second and third copies to ensure dominance.
As usual, a proper coloring of the copies is both necessary and sufficient. If we use fewer colors than required, at least one vertex will fail to dominate any color class, including its own. Thus, upon simplification, we obtain \(\chi_{d}(C_n \bullet G) \geq 2 \chi_d(C_n)+3\chi(G)-4\).
Subcase ii. This case is considered when n is odd. Consider the following for all values of \(n\geq 7\):
\(\bullet\) When s is odd and for \(1\leq t \leq m\): \[\varphi(b_t^s) = \{2\} \cup \{ \chi_d(C_n)+1, \chi_d(C_n)+2, \cdots, \chi_d(C_n)+\chi(G)-1\}.\]
\(\bullet\) When s=n and for \(1\leq t \leq m\): \[\varphi(b_t^s) = \{ \chi_d(C_n)+\chi(G), \chi_d(C_n)+\chi(G)+1, \cdots, \chi_d(C_n)+2\chi(G)-1\}.\]
\(\bullet\) When s is even and for \(1\leq t \leq m\): \[\varphi(b_t^s) = \{1\} \cup \{\chi_d(C_n)+2\chi(G, \chi_d(C_n)+2\chi(G)+1, \cdots, \chi_d(C_n)+3\chi(G)-2\}.\]
\(\bullet\) When \(s\equiv 2(mod \ 3)\) and for atleast one value of t: \[\varphi(b_t^s) = \chi_d(C_n)+3\chi(G)-2+\lceil{\frac{s}{3}}\rceil.\]
In the last consideration, the value of \(t\) is selected based on the specific structure of the graph and its proper coloring. However, when \(s \equiv 2 \ (mod \ 3)\), it is necessary to color at least one vertex with a distinct color.
In this case, particularly for \(1 \leq s \leq m-3\) when \(n \equiv 0 \ (mod \ 3)\), the following adjustments are required instead of the previously mentioned subcase for particular values of \(s\).
\(\bullet\) When s is even, \(1\leq s \leq m-3\) and for \(1\leq t \leq m\): \[\varphi(b_t^s) = \{1\} \cup \{\chi_d(C_n)+\chi(G), \chi_d(C_n)+\chi(G)+1, \cdots, \chi_d(C_n)+2\chi(G)-2 \}.\]
As before, in each scenario, we properly utilize the colors from the given set for every copy. Since \(C_n\) is assigned a dominator coloring, the unique coloring sequence of vertices is similarly applied to their respective copies in this case also, confirming that all vertices in the product graph dominate at least one color class, denoted as \(\phi_i\). This way of dominator coloring yields a total of \(2 \chi_d(C_n)+3\chi(G)-5\) colors demonstrating that \(\chi_{d}(C_n \bullet G) \leq 2 \chi_d(C_n)+3\chi(G)-5\).
It remains to validate the lower bound.
For every \(s\), a proper coloring of the vertex copies is necessary.
Since in an odd cycle, the first and the last vertices are assigned distinct colors, the \(n^{th}\) vertex copy requires a complete set of different colors than those repeated for every odd copy.
Since a dominator coloring of the cycle \(C_n\) assigns a unique color to every \(s^{th}\) vertex, when \(s \equiv 2(mod \ 3)\), similar to the previous case, a unique color must also be applied to every \(s^{th}\) copy of \(G\) when \(s\equiv 2(mod \ 3)\), in addition to the dominator coloring of \(C_n\).
The special case when \(n\equiv 0(mod \ 3)\) arises because, the \((n-1)^{th}\) vertex is necessarily assigned a distinct color, given that, \(n-1 \equiv 2(mod \ 3).\) This permits the re-usage of colors given to the last copy wherever applicable. We can reuse these colors for every odd copy, without disrupting the proper coloring.
If we use fewer colors than this number, at least one vertex will fail to dominate any color class, including its own. Therefore, to ensure dominance, we need at least \(2 \chi_d(C_n)+3\chi(G)-5\) colors to achieve dominance. Thus, \(\chi_{d}(C_n \bullet G)\geq 2 \chi_d(C_n)+3\chi(G)-5,\) when n is odd.
An example illustrating this case is shown in Figure 2, which depicts the extended corona product of the cycle \(C_7\) with the star \(K_{1,3}\).
Case iv. When n \(\equiv\) 1(mod 3), n is even and otherwise.
This case is examined through two subcases as follows.
Subcase i. When n \(\equiv\) 1(mod 3), n is even
For the even values of \(n\), the proof is almost similar to the latter case of Theorem 3.1. Consider the following transformation:
\(\bullet\) When s is odd and for \(1\leq t \leq m\): \[\varphi(b_t^s) = \{2\} \cup \{ \chi_d(C_n)+1, \chi_d(C_n)+2, \cdots, \chi_d(C_n)+\chi(G)-1\}.\]
\(\bullet\) When s is even and for \(1\leq t \leq m-1\): \[\varphi(b_t^s) = \{1\} \cup \{\chi_d(C_n)+\chi(G, \chi_d(C_n)+\chi(G+1), \cdots, \chi_d(C_n)+2\chi(G)-2\}.\]
\(\bullet\) When \(s\equiv 2(mod \ 3)\) and for atleast one value of t: \[\varphi(b_t^s) = \chi_d(C_n)+2\chi(G)-2+\lceil{\frac{s}{3}}\rceil.\]
In the same way, the value of \(t\) in the final consideration is determined by the specific structure of the graph and its proper coloring. However, when \(s \equiv 2 \ (mod \ 3)\), it becomes essential to color at least one vertex with a distinct color. In every scenario, we effectively use the colors from the given set for each copy. Similarly, since \(C_n\) has a dominator coloring, its unique vertex coloring extends to the corresponding copies. This ensures that all vertices dominate at least one color class \(\phi_i\) as seen in the previous instances. This way of dominator coloring results in a total of \(2 \chi_d(C_n)+3\chi(G)-5\) colors proving that \(\chi_{d}(C_n \bullet G) \leq 2 \chi_d(C_n)+3\chi(G)-5\).
It remains to show that \(\chi_{d}(C_n \bullet G) \geq 2 \chi_d(C_n)+3\chi(G)-5.\)
For every \(s\), a proper coloring of the vertex copies is necessary.
Since a dominator coloring of cycle \(C_n\) assigns a unique color to every \(s^{th}\) vertex, when \(s \equiv 2(mod \ 3)\), similar to the previous theorem, in addition to the dominator coloring of \(C_n\), a unique color must also be applied to every \(s^{th}\) copy of \(G\), when \(s\equiv 2(mod \ 3)\).
As observed in the path case, the \(n^{th}\) vertex is assigned a unique color in the dominator coloring of \(C_n\), while the remaining \(n-1\) colors are grouped in threes, with the central vertex of each group receiving a unique color. Thus, it is not necessary to assign a unique color to the last vertex copy. This explains why the dominator chromatic number is different in this scenario, particularly when \(n\equiv 1(mod \ 3).\)
As usual, if we use fewer colors than this number, at least one vertex will fail to dominate any color class, including its own. Therefore, to ensure dominance, we need at least \(2 \chi_d(C_n)+3\chi(G)-5\) colors to achieve dominance. Thus, \(\chi_{d}(C_n \bullet G)\geq 2 \chi_d(C_n)+3\chi(G)-5,\) when n is even.
Subcase ii. Otherwise.
Since \(n\) is an even number with the additional condition that \(n \not \equiv 1 (mod \ 3)\), the proof follows directly from the previous sub-case. The only distinction lies in the requirement for unique colors for each \(s^{th}\) copy when \(s \equiv 2 (mod \ 3)\). The number of distinct colors required for every \(s^{th}\) copy, when \(s\equiv 2(mod \ 3)\) is one greater than the number used when \(n\equiv 1(mod \ 3)\), while the transformations, the lower and upper bounds clearly follow from the sub-case i. ◻
In this section, we determine the dominator chromatic number of the closed neighborhood corona product of any two connected graphs.
Definition 3.3. [16] The closed neighborhood corona \(G_1 \boxtimes G_2\) of any two graphs \(G_1\) and \(G_2\) is a new graph obtained by creating \(|V(G_1)|\) copies of \(G_2\) and joining each vertex of the \(s^{th}\) copy of \(G_2\) to the \(s^{th}\) vertex and the neighborhood of the \(s^{th}\) vertex of \(G_1\).
Theorem 3.4.The dominator chromatic number of the closed neighborhood corona of any two graphs \(G_1\) and \(G_2\) is \[\chi_{d}(G_1 \boxtimes G_2)= \chi_d(G_1)+\chi(G_2).\]
Proof. Let \(G_1\) and \(G_2\) be two connected graphs of order \(n\) and \(m\), respectively. As usual, define the vertex sets as \(V(G_1)=\{a_s:1\leq s \leq n\}\) and \(V(G_2)=\{b_t:1\leq t \leq m\}\). For each \(s\), associate a copy of \(G_2\), denoted as \(G_2^s\), with vertex labels \(V(G_2^s)=\{b_t^s : 1\leq s \leq n, 1\leq t \leq m\}\). Consequently, the vertex set of the product graph is \(V(G_1 \boxtimes G_2) = V(G_1) \cup V(G_2^s)\), resulting in a total of \(n(m+1)\) vertices.
Define a function \(\varphi : V(G_1 \boxtimes G_2) \rightarrow \{1,2,\cdots, \chi_{d}(G_1 \boxtimes G_2)\}\). Start by coloring the vertices of the first graph \(G_1\) using its dominator coloring, assigning colors such that \(\varphi(a_s)=\{1,2,\cdots,\chi_d(G_1)\}\). Next, for each \(s\), restrict \(\varphi\) to \(G_2^s\) with a \(\chi(G_2)\)-coloring as follows:
Every vertex in the \(s^{th}\) copy of \(G_2\) properly uses colors from the following set: \[\{\chi_d(G_1)+1, \chi_d(G_1)+2, \cdots, \chi_d(G_1)+\chi(G_2)\}.\]
This makes \(\varphi\) a dominator coloring of \(G_1 \boxtimes G_2\). Since \(G_1\) has been assigned a dominator coloring, each vertex in \(V(G_1)\) dominates a color class, denoted \(\phi_i\), for \(1\leq i \leq \chi_d(G_1 \boxtimes G_2)\). According to the definition 3.3, each vertex in the \(s^{th}\) copy of \(G_2\) is connected to the \(s^{th}\) vertex and its neighbors, ensuring that every vertex in the \(s^{th}\) copy of \(G_2\) dominates the same color class \(\phi_i\) in the same way the corresponding vertex \(a_s\) in \(G_1\) does. Thus, we conclude that \(\chi_{d}(G_1 \boxtimes G_2) \leq \chi_d(G_1)+\chi(G_2)\).
We need to demonstrate that \(\chi_{d}(G_1 \boxtimes G_2) \geq \chi_d(G_1)+\chi(G_2)\). Mapping the vertices of \(G_1\) is crucial for achieving dominance. This is straightforward because the \(s\)-copies, created according to the product definition, are simply multiples of the vertices \(a_s\) from \(G_1\) with the same adjacency. If we do not use dominator coloring for the vertices of \(G_1\), we risk undermining the dominating behavior of each vertex and its copies. Therefore, we can conclude that \(\chi_{d}(G_1 \boxtimes G_2) \geq \chi_d(G_1)\).
Moreover, we cannot reassign colors from the set \(\{1,2,\cdots,\chi_d(G_1)\}\) to the vertex copies due to adjacency constraints. To maintain a proper coloring, all vertex copies must be assigned colors greater than \(\chi_d(P_n)\). A proper coloring of these vertex copies, as mentioned, is necessary. Therefore, we require a total of \(\chi(G_2)\) new colors, each exceeding \(\chi_d(G_1)\), which establishes that \(\chi_{d}(G_1 \boxtimes G_2) \geq \chi_d(G_1)+\chi(G_2)\).
An example is provided in the Figure 3 that depicts the closed neighborhood corona product of the wheel graph \(W_{1,3}\) with the star \(K_{1,3}\). ◻
This section introduces a new graph product known as the closed extended neighborhood corona product for any two connected graphs. Additionally, we determine the dominator chromatic number for this product involving any two graphs.
Definition 3.5. The closed extended neighborhood corona \(G_1 \boxplus G_2\) of any two graphs \(G_1\) and \(G_2\), is a new graph obtained by taking \(|V(G_1)|\) copies of \(G_2\). Each vertex in the \(s^{th}\) copy of \(G_2\) is then connected to the \(s^{th}\) vertex of \(G_1\), followed by taking the extended neighborhood corona of \(G_1\) and \(G_2\).
Theorem 3.6. The dominator chromatic number of the closed exatended neighborhood corona of any two connected graphs \(G_1\) and \(G_2\) is \[\chi_{d}(G_1 \boxplus G_2)= \chi_d(G_1)+ \chi(G_1) \chi(G_2).\]
Proof. Let \(G_1\) and \(G_2\) be two connected graphs with order \(n\) and \(m\) respectively. The remaining notations are followed from the Theorem 3.4.
Define a function \(\varphi : V(G_1 \boxplus G_2) \rightarrow \{1,2,\cdots, \chi_{d}(G_1 \boxplus G_2)\}\). Following the approach of previous theorems, begin by coloring the vertices of the first graph \(G_1\) using its dominator coloring, ensuring that \(\varphi(a_s)=\{1,2,\cdots,\chi_d(G_1)\}\). Next, for each \(s\), restrict \(\varphi\) to \(G_2^s\) with a \(\chi(G_2)\)-coloring as follows:
Assume that \(\chi(G_1)\) is a proper coloring that assigns colors from the set \(\{1,2, \cdots,\chi(G_1)\}\) to the vertices in \(V(G_1)\). This results in \(k\) number of color classes denoted as \(\phi(k)\), where \(1\leq k\leq \chi(G_1).\)
Let \(k\) represent the color assigned to the vertex \(a_s\) in the graph \(G_1\) under its proper coloring. Based on the value of \(k\), the vertices in each \(s^{th}\) copy of \(G_2\) are properly assigned colors from the following set: \[\{\chi_d(G_1) + (k-1)\chi(G_2) + 1, \chi_d(G_1) + (k-1)\chi(G_2) + 2, \cdots, \chi_d(G_1)+ k\chi(G_2)\}.\]
This confirms that \(\varphi\) is indeed a dominator coloring of \(G_1 \boxplus G_2\). Since \(G_1\) has been assigned a dominator coloring, each vertex in \(V(G_1)\) dominates a color class, denoted by \(\phi_i\), for \(1 \leq i \leq \chi_d(G_1 \boxplus G_2)\). According to the definition 3.5, each vertex in the \(s^{th}\) copy of \(G_2\) is connected to the \(s^{th}\) vertex of \(G_1\), its neighbors and its copies. This guarantees that every vertex in the \(s^{th}\) copy of \(G_2\) dominates the same color class \(\phi_i\) in the same manner as the corresponding vertex \(a_s\) in \(G_1\). Furthermore, distinct colors are required for each adjacent copy to maintain a proper coloring. Therefore, we conclude that \(\chi_d(G_1 \boxplus G_2) \leq \chi_d(G_1) + \chi(G_1)\chi(G_2)\).
We aim to show that \(\chi_{d}(G_1 \boxplus G_2) \geq \chi_d(G_1)+\chi(G_1)\chi(G_2)\). As discussed in the previous theorem, mapping the vertices of \(G_1\) is essential for achieving dominance. This is evident because the \(s\)-copies, defined according to the product definition, are simply multiples of the vertices \(a_s\) from \(G_1\) with the same adjacency. Failing to employ dominator coloring for the vertices of \(G_1\), we risk compromising the dominating behavior of each vertex and its copies. Therefore, we can conclude that \(\chi_{d}(G_1 \boxtimes G_2) \geq \chi_d(G_1)\).
Furthermore, we cannot reassign colors from the set \(\{1,2,\cdots,\chi_d(G_1)\}\) to the vertex copies because of adjacency constraints. To ensure a proper coloring, all vertex copies must be assigned colors greater than \(\chi_d(G_1)\). This proper coloring of the vertex copies is essential. Additionally, according to the definition, each \(s^{th}\) copy is completely connected to the copies of its neighboring vertices, making it impossible to reuse the same color set for all copies. Consequently, we need a total of \(\chi(G_1)\chi(G_2)\) new colors to maintain a proper coloring, each exceeding \(\chi_d(G_1)\), which proves that \(\chi_{d}(G_1 \boxplus G_2) \geq \chi_d(G_1)+\chi(G_1)\chi(G_2)\).
An example is provided in the Figure 4 that depicts the closed extended neighborhood corona product of the complete graph \(K_{4}\) with the cycle \(C_{3}\).
In conclusion, this research has introduced and explored the closed extended neighborhood corona of two graphs, providing exact values for its dominator chromatic number for any pair of connected graphs. Additionally, the dominator chromatic number for specific graph products, such as the extended corona of the path and cycle with any graph and the closed neighborhood corona of any two connected graphs has been determined. These findings contribute to a deeper understanding of graph products and dominator coloring, opening avenues for future research in this area.
The authors declare no conflicts of interest.