Dominator Colorings of Certain Cartesian Products of Paths and Cycles

Abstract

A dominator coloring of a graph G is a proper coloring of G with the additional property that every vertex dominates an entire color class. The dominator chromatic number $\chi _d(G)$ of G is the minimum number of colors among all dominator colorings of G. In this paper, we determine the dominator chromatic numbers of Cartesian product graphs $P_2 \square P_n$ and $P_2 \square C_n$.

1 Introduction

All graphs considered in this paper are finite, undirected and simple. Let $G=(V,E)$ be a graph with vertex set V and edge set E. The open neighborhood of a vertex $v\in V$ is $N(v)=\{u\in V|uv\in E\}$ and the closed neighborhood of v is $N[v]=\{v\}\cup N(v)$. Any vertex of G is said to dominate itself and all its neighbors. A subset D of V is a dominating set if every vertex not in D is adjacent to at least one vertex in D. The domination number $\gamma (G)$ is the minimum cardinality of a dominating set of G.

A proper coloring of G is a mapping f :  $V(G)\rightarrow \{1,2,\ldots , k\}$ such that adjacent vertices receive distinct colors. The chromatic number $\chi (G)$ of G is the minimum number of colors needed for a proper coloring of G. A color class is the set consisting of all those vertices assigned the same color. If there is only one vertex in some color class, we call it a singleton color class.

A dominator coloring of G is a proper coloring such that every vertex of G dominates all vertices of at least one color class (possibly its own class). The dominator chromatic number, denoted by $\chi _d(G)$, of G is the minimum number of colors needed for a dominator coloring of G. Obviously, $\chi (G)\le \chi _d(G)$. For a nonegative integer k, a k-dominator coloring is a proper dominator coloring using at most k colors. The definition of dominator coloring was first introduced by Gera et al. [3]. She also proved that computing the dominator chromatic number of a graph is NP-hard for general graphs. In [4], Gera showed that every graph satisfies:

$$\begin{aligned} \max \{\gamma (G),\chi (G)\}\le \chi _d(G)\le \gamma (G)+\chi (G). \end{aligned}$$

(1)

For more results on dominator coloring, we refer the reader to [1, 2, 5, 7].

The Cartesian product graph $P_2 \square P_n$ has vertex set $V(P_2\square P_n)=\{v_1,v_2,\ldots ,v_n;u_1, u_2,\ldots ,u_n\}$ and edge set $E(P_2\square P_n)=\{v_iv_{i+1}:1\le i\le n-1\}\cup \{u_iu_{i+1}:1\le i\le n-1\}\cup \{u_iv_i:1\le i\le n\}$. If we add two edges $v_1v_n$ and $u_1u_n$ to $P_2\square P_n$, the resulting graph is denoted by $P_2\square C_n$. The purpose of this paper is to study the dominator colorings for $P_2 \square P_n$ and $P_2\square C_n$. More precisely, We prove that

Theorem 1

For $n\ge 2$, $\chi _d(P_2\square P_n)=\left\{ \begin{array}{ll} 2 &{} \quad {\text { if }}n=2; \\ 4 &{} \quad {\text { if }}n=4; \\ \lfloor n/2\rfloor +3 &{} \quad {\text { if }}n=3{\text { and }}n\ge 5. \end{array} \right.$

Theorem 2

For $n\ge 3$, $\chi _d(P_2\square C_n)=\left\{ \begin{array}{ll} 3 &{} \quad {\text { if }}n=3; \\ 2\lfloor n/4\rfloor +2 &{} \quad {\text { if }}n\equiv 0\pmod 4; \\ 2\lfloor n/4\rfloor +3 &{} \quad {\text { if }}n\equiv 1\pmod 4;\\ 2\lfloor n/4\rfloor +4 &{} \quad {\text { if }}n\equiv 2,3\pmod 4. \end{array} \right.$

2 Preliminaries

A clique in a graph G is a complete subgraph of G. Let f be a proper coloring of G and $S\subset V$. If color a appears on no other vertices but S, then we say that S consumes color a.

Gera [4] pointed out that given a graph G and a subgraph H, the dominator coloring numbers $\chi _d(H)$ can be smaller or larger than $\chi _d(G)$. Next, we present a sufficient condition to guarantee that $\chi _d(H)\le \chi _d(G)$. For any subset $S\subset V$, $G\backslash S$ is the graph obtained from G by removing S and all edges incident with vertices in S. Let G[S] denote the subgraph induced by S in G.

Lemma 1

Let $G=(V,E)$ be a graph and $S\subset V$. Write $V'=\{v_i|v_i\in V\backslash S~\text{ and }~N(v_i)\cap S\ne \emptyset \}$. If $G[V']$ is a clique, then $\chi _{d}(G\backslash S)\le \chi _d(G)$.

Proof

Let f be a $\chi _d$-dominator coloring of G. Suppose that the restriction of f to $G\backslash S$ is not a dominator coloring of $G\backslash S$, then it must be the case that the dominated color class of some vertex $v\in V'$ is totally contained in S. Now recolor v by this color. Then $\{v\}$ is a singleton color class. If there exist at least two vertices in $V'$ that dominate the same color class in S, then arbitrarily choose one vertex among them and recolor it by that color. Obviously, the resulting coloring is a $\chi _d$-dominator coloring of $G\backslash S$. $\square$

If we take $S=\{u_{m+1},\ldots ,u_{n};v_{m+1},\ldots , v_n\}$ in $P_2\square P_n$, then the following is an easy consequence of Lemma 1.

Corollary 1

If $n\ge m$, then $\chi _d(P_2\square P_n)\ge \chi _d(P_2\square P_m)$.

Lemma 2

Let f be a $\chi _d$-dominator coloring of $P_2\Box P_n$. If there is no singleton color class under f, then the color classes of $P_2\Box P_n$ must be in the form of $\{v_i,u_{i+1}\}$ or $\{u_i,v_{i+1}\}$, where $i=1,2,\ldots ,n-1$.

Proof

Without loss of generality, we assume that $f(v_1)=1$. Since there is no singleton color class, then $v_1$ dominates color class $\{u_1, v_2\}$. So $f(u_1)=f(v_2)$. Assume that $f(u_1)=f(v_2)=2$. By exchanging the roles of $u_1$ and $v_1$, we have that $f(v_1)=f(u_2)=1$ and $u_1$ dominates color class $\{v_1, u_2\}$. Now, colors 1 and 2 cannot be used on other vertex any more. Using a similar argument, we can get that all the color classes are in the form of $\{v_i,u_{i+1}\}$ and $\{u_i,v_{i+1}\}$. $\square$

Corollary 2

Let f be a $\chi _d$-dominator coloring of $P_2\Box P_n$. If there is no singleton color class under f, then n is even.

We close this section with some known results.

Lemma 3

([4]) For the cycle $C_n$, we have $\chi _{d}(C_n)=\left\{ \begin{array}{ll} \lceil n/3\rceil , &{} \quad {\text {if }}n=4; \\ \lceil n/3\rceil +1, &{} \quad {\text {if }}n=5; \\ \lceil n/3\rceil +2, &{} \quad {\text {otherwise}}. \end{array} \right.$

Lemma 4

([6]) For $n\ge 1$, $\gamma (P_2\square P_n)=\lfloor (n+2)/2\rfloor$.

Lemma 5

([8]) For $n\ge 3$, $\gamma (P_2\square C_n)=\left\{ \begin{array}{ll} \lceil (n+1)/2\rceil , &{} \quad {\text {if }}n{\text { is not a multiple of 4;}} \\ n/2, &{} \quad {\text {if }}n{\text { is a multiple of 4}}. \end{array} \right.$

3 Dominator Colorings for $P_2\square P_n$

In this section, we determine $\chi _d(P_2\square P_n)$ for all $n\ge 2$. We first consider the cases for $n\le 4$.

Lemma 6

For $n\le 4$, we have $\chi _d(P_2\square P_n)$= $\left\{ \begin{array}{ll} 2, &{} \quad {\text {n = 2;}} \\ 4, &{} \quad {\text {n = 3,4.}} \end{array} \right.$

Proof

Since $P_2\square P_2$ is isomorphic to $C_4$, the result follows from Lemma 3. If $n=3$, then by Lemma 4 and the right side of inequality (1), we have $\chi _d(P_2\square P_3)\le 2+2=4$. Next, we show that $\chi _d(P_2\square P_3)\ge 4$.

Assume to the contrary that f is a dominator coloring of $P_2\Box P_3$ using at most three colors. It follows from Corollary 2 that there is at least one singleton color class under f. By symmetry, we distinguish the following two cases.

Fig. 1

A 4-dominator coloring of $P_2\square P_4$

Case 1. $\{v_1\}$ is a singleton color class.

Without loss of generality, we assume that $f(v_1)=1$. If $f(u_1)\ne f(v_2)$, then $u_2$ cannot be properly colored. So assume $f(u_1)=f(v_2)=2$. Then we have $f(u_2)=3$, $f(u_3)=2$ and $f(v_3)=3$. However, in this case $v_3$ does not dominate any color class, a contradiction.

Case 2. $\{v_2\}$ is a singleton color class.

Assume that $f(v_2)=1$. If $f(v_1)\ne f(u_2)$, then $u_1$ cannot be properly colored. So assume that $f(v_1)=f(u_2)=2$. It follows that $f(u_1)=f(u_3)=3$ and $f(v_3)=2$. However, in this case $u_3$ does not dominate any color class, a contradiction.

By Corollary 1, we have $\chi _d(P_2\square P_4)\ge \chi _d(P_2\square P_3)=4$. On the other hand, a 4-dominator coloring is shown in Fig. 1. Hence $\chi _d(P_2\square P_4)=4$. This completes the proof. $\square$

The rest of this section is devoted to proving Theorem 1 for $n\ge 5$. By Lemma 4 and the right side of inequality (1), we have that $\chi _d(P_2\square P_n)\le \lfloor (n+2)/2\rfloor +2=\lfloor n/2\rfloor +3$. Hence, it suffices to show $\chi _d(P_2\square P_n)\ge \lfloor n/2\rfloor +3$ in the sequel. In our proof, we will use the following claim. First, we give one more notation: for $k\le n$, define $G_k$ to be the subgraph of $P_2\square P_n$ induced by $\{u_1,\ldots ,u_k;v_1,\ldots ,v_k\}$.

Claim

Let $G=P_2\square P_n$ and let f be a dominator coloring of G. If $\{u_k\}$ or $\{v_k\}$ is a singleton color class for some $k\le n$, then the restriction of f to $G_k$ is a dominator coloring of $G_k$.

Proof

By symmetry, we assume that $\{u_k\}$ is a singleton color class. Then both $u_k$ and $v_k$ dominate color class $\{u_k\}$ in $G_k$, and for vertex $v\in V(G_k){\setminus } \{u_k,v_k\}$, v dominates the same color class as that in G. Thus the claim follows. $\square$

Lemma 7

For the path $P_5$, we have $\chi _d(P_2\square P_5)\ge 5$.

Proof

Suppose to the contrary that f is a dominator coloring of $P_2\Box P_5$ using at most four colors. By Corollary 2, there is at least one singleton color class under f. Let k be the smallest integer such that $\{u_k\}$ or $\{v_k\}$ is a singleton color class of $P_2\square P_5$. Then by our claim, the restriction of f on $G_k$ is a dominator coloring of $G_k$. By symmetry, we distinguish among three cases.

Case 1. $k=3$.

By Lemma 6, at least four colors appear on $G_3$. So $f(v_5)$, $f(u_5)$ and $f(u_4)$ are reused colors in $G_3$, which implies that $u_5$ does not dominate any color class, a contradiction.

Case 2. $k=4$.

Again by Lemma 6, four colors all appear on $G_4$. Assume without loss of generality that $\{u_4\}$ is a singleton color class. Since $f(u_5)$ and $f(v_5)$ are reused colors in $P_2\Box P_4$, then either $v_5$ dominates color class $\{u_5,v_4\}$ or $\{v_4\}$ is a singleton color class. In both cases, we only have two remaining colors to color $G_4$. It is easy to check that in this case $u_1$ does not dominate any color class.

Case 3. $k=1$.

By symmetry we may assume without loss of generality that $\{u_1\}$ is a singleton color class. Then neither $u_5$ nor $v_5$ is a singleton color class, otherwise $u_3$ can not dominate any color class. Combining the above two cases, we obtain that there is no singleton color class in the form of $\{u_k\}$ or $\{v_k\}$ for $k=2,3,4,5$. By the same argument as in the proof of Lemma 2 , we have that $\{u_5,v_4\}$, $\{v_5,u_4\}$, $\{u_3,v_2\}$ and $\{v_3,u_2\}$ are four color classes. Then there is no color that can be assigned to vertices $v_1$ and $u_1$, a contradiction. $\square$

Lemma 8

For the path $P_6$, we have $\chi _d(P_2\square P_6)\ge 6$.

Proof

Suppose to the contrary that f is a dominator coloring of $P_2\Box P_6$ using at most five colors. If there is no singleton color class under f, then by Lemma 2, six colors are needed for f, a contradiction. So there is at least one singleton color class. Let k be the smallest integer such that $\{u_k\}$ or $\{v_k\}$ is a singleton color class of $P_2\square P_6$. Then by our claim, the restriction of f on $G_k$ is a proper dominator coloring of $G_k$. By symmetry, we distinguish among three cases.

Case 1. $k=5$.

Without loss of generality, we assume that $\{v_5\}$ is a singleton color class, say $f(v_5)=5$. Then by our claim the restriction of f on $G_5$ is a dominator coloring of $G_5$. According to Lemma 7, five colors all appear on $G_5$. Then $f(u_6)$ and $f(v_6)$ both are reused colors on $G_5$. Therefore, either $\{u_5\}$ is a singleton color class, or $\{u_5, v_6\}$ consists a color class dominated by $u_6$.

Subcase 1.1. $\{u_5\}$ is a singleton color class, say $f(u_5)=4$. Since $N[u_2]$ consumes at least one color, we have at most two colors to color the vertices in set $\{v_3,v_4,u_4,v_6,u_6\}$. Without loss of generality, let $f(v_3)=f(u_4)=1$ and $f(v_4)=2$. As $\{f(v_6),f(u_6)\}=\{1,2\}$, $v_3$ does not dominate color class $\{f^{-1}(1)\}$ or $\{f^{-1}(2)\}$. So $\{v_2, u_3\}$ consumes color 3. This implies that $\{f(u_1), f(u_2),f(v_1)\}=\{1,2\}$. However, in this case $u_1$ does not dominate any color class, a contradiction.

Subcase 1.2. $\{u_5, v_6\}$ consists a color class, say $f(u_5)=f(v_6)=4$. Since $N[u_4]$ consumes at least one color, we only have two remaining colors to color the vertices in set $\{u_1,u_2,v_1,v_2,v_3\}$. Then we can see that $u_1$ does not dominate any color class, a contradiction.

Case 2. $k=3$.

Now the restriction of f on $G_3$ is a proper dominator coloring of $G_3$. By Lemma 6, there are at least four colors on $G_3$. If $\{u_6\}$ is a singleton color, then $f(v_4),f(v_5), f(v_6)$ and $f(u_5)$ are reused colors on $G_3$. This implies that $v_5$ does not dominate any color class, a contradiction. So $f(u_6)$ is a reused color in $P_2\Box P_6$. Using a similarly argument, we can prove that $f(u_5)$ is also a reused color in $P_2\Box P_6$. By symmetry, we have that $f(v_5)$ and $f(v_6)$ both are reused colors in $P_2\Box P_6$. Then $\{v_5,u_6\}$ and $\{v_6,u_5\}$ are two new color classes, a contradiction.

Combining Cases 1 and 2, we know that there is no singleton color class in the form of $\{u_k\}$ or $\{v_k\}$ for $k=2,3,4,5$.

Case 3. $k=1$.

Suppose $\{u_1\}$ is a singleton color class. If neither $\{u_6\}$ nor $\{v_6\}$ is a singleton color class, we know that $\{u_5,v_6\}$, $\{v_5,u_6\}$, $\{u_3,v_4\}$ and $\{v_3,u_4\}$ are four color classes. Then there is no color that can be assigned to vertices $v_1$ and $v_2$, a contradiction. So at least one of $\{u_6\}$ and $\{v_6\}$ is singleton. If $\{u_6\}$ is singleton, then since $N[v_5]$ consume at least one color class, we only have two colors to color the vertices in set $\{v_1,v_2,v_3,u_2,u_3,u_4\}$. It is easy to check that in this case $u_3$ does not dominate any color class, a contradiction. The same result holds when $\{v_6\}$ is singleton. $\square$

Lemma 9

For $n\ge 7$, we have $\chi _d(P_2\square P_n)\ge \lfloor n/2\rfloor +3$.

Proof

Our proof proceeds by induction on n. For $n=7$, by Corollary 1 and Lemma 8, we have $\chi _d(P_2\Box P_7)\ge 6$.

So the lemma holds for $n=7$. Assume that $\chi _d(P_2\square P_n)\ge \lfloor n/2\rfloor +3$ holds for $n< k$.

When $n=k$, if $n=2t+1$ is odd, then $\chi _d(P_2\Box P_n)\ge \chi _d(P_2\Box P_{n-1})=\lfloor (n-1)/2\rfloor +3= \lfloor n/2\rfloor +3$.

In what follows, we deal with the case when n is even. First notice that by induction assumption, $\chi _d(P_2\Box P_{n-3})\ge \lfloor (n-3)/2\rfloor +3=\lfloor n/2\rfloor +1$ and $\chi _d(P_2\square P_{n-1})\ge \chi _d(P_2\square P_{n-2})=\lfloor (n-2)/2\rfloor +3=\lfloor n/2\rfloor +2$. Suppose to the contrary that $\chi _d(P_2\Box P_{n})\le \lfloor n/2\rfloor +2$.

Case 1. Neither $\{u_{n-2}\}$ nor $\{v_{n-2}\}$ is a singleton color class.

So the restriction of f on $G_{n-3}$ is a proper dominator coloring. By inductive hypothesis, at least $\lfloor n/2\rfloor +1$ colors are used to color the vertices of $G_{n-3}$.

• 1. If $\{u_n\}$ is a singleton color class, then $f(v_{n-2}), f(v_n), f(v_{n-1})$ and $f(u_{n-1})$ are reused colors on $G_{n-3}$. In this case $v_{n-1}$ cannot dominate any color class, a contradiction. By symmetry, we have that $\{v_n\}$ is not a singleton color class either.

• 2. If $\{u_{n-1}\}$ is a singleton color class, then $f(u_{n}), f(v_n)$ and $f(v_{n-1})$ are reused colors on $G_{n-3}$. In this case $v_{n}$ does not dominate any color class, a contradiction. By symmetry, we have that $\{v_{n-1}\}$ is not a singleton color class either.

Combining (1) and (2), we have that $v_n$ dominates color class $\{u_n,v_{n-1}\}$ and $u_n$ dominates color class $\{v_n,u_{n-1}\}$. That is, we need two more colors to color the vertices outside $G_{n-3}$, a contradiction.

Case 2. At least one of $\{u_{n-2}\}$ and $\{v_{n-2}\}$ is a singleton color class.

Fig. 2

A 3-dominator coloring of $P_2\square C_3$

Fig. 3

A 5-dominator coloring of $P_2\square C_5$

Fig. 4

A 6-dominator coloring of $P_2\square C_7$

Then the restriction of f on $G_{n-2}$ is a dominator coloring. By inductive hypothesis, at least $\lfloor n/2\rfloor +2$ colors appear on $G_{n-2}$. Then $f(u_{n}), f(v_n)$ and $f(u_{n-1})$ are reused colors on $G_{n-2}$. This implies that $u_n$ does not dominate any color class, a contradiction. This completes the proof. $\square$

4 Dominator Colorings for $P_2\square C_n$

In this section, we determine $\chi _d(P_2\square C_n)$ for all $n\ge 3$.

Lemma 10

For the cycle $C_3$, we have $\chi _d(P_2\square C_3)=3$.

Proof

A 3-dominator coloring of $P_2\Box C_3$ is depicted in Fig. 2. On the other hand, $\chi _d(P_2\Box C_3)\ge \chi (P_2\Box C_3)=3$. $\square$

If $n\ge 4$ is even, then by Lemma 5 and the right side of inequality (1), it follows that

$$\begin{aligned} \chi _d(P_2\square C_n)\le \left\{ \begin{array}{ll} 2\lfloor n/4\rfloor +2 &{} \quad {\text { if }}n\equiv 0\pmod 4; \\ 2\lfloor n/4\rfloor +4 &{} \quad {\text { if }}n\equiv 2\pmod 4. \end{array} \right. \end{aligned}$$

So to prove Theorem 2 when n is even, we only need to show the inverse direction. First, we give an important observation, which is applied frequently in the following proofs (see Figs. 3, 4).

Observation 1

Let f be a dominator coloring of $P_2\square C_n$. For each i, let $T_i=\{u_i, u_{i+1}, u_{i+2}, u_{i+3}, v_{i+1}, v_{i+2}, v_{i+3}, v_{i+4}\}$ (index mod n). We will show that there are at least four colors in the restriction of f on $T_i$. Indeed, if at most three colors appear on $T_i$, since $N[v_{i+3}]$ consumes at least one color, at most two colors appear on $N[u_{i+1}]$. Without loss of generality, let $f(u_{i+1})=1$ and $f(u_i)=f(u_{i+2})=f(v_{i+1})=2$. By a similar argument, there are at most two colors on $N[v_{i+3}]$, one of which must be 1 or 2. If color 2 appears on $N[v_{i+3}]$, then we have $f(v_{i+3})=2$ and $f(v_{i+2})=f(u_{i+3})=f(v_{i+4})=3$. If color 1 appears on $N[v_{i+3}]$, then either $f(v_{i+3})=3$ and $f(v_{i+2})=f(u_{i+3})=f(v_{i+4})=1$ or $f(v_{i+3})=1$ and $f(v_{i+2})=f(u_{i+3})=f(v_{i+4})=3$. It is easy to check that either $u_{i+2}$ or $v_{i+2}$ does not dominate any color class in these cases.

Lemma 11

For $n\equiv 0\bmod 4$, we have $\chi _d(P_2\square C_n)\ge 2\lfloor n/4\rfloor +2$.

Proof

By Observation 1, at least four colors appear on $T_1$, and when $n\ge 8$, $N[u_6]\cup N[v_8]\cup N[u_{10}]\cdots \cup N[v_{n}]$ consume at least $(n-4)/2$ colors. Hence at least $(n-4)/2+4=2\lfloor n/4\rfloor +2$ colors appear on $P_2\Box C_n$. Then $\chi _d(P_2\square C_n)\ge 2\lfloor n/4\rfloor +2$. $\square$

Lemma 12

Let f be a dominator coloring of $P_2\square C_n$, $n\ge 5$. If there is no singleton class under f, then $f(u_1)\ne f(u_3)$.

Proof

Assume to the contrary that $f(u_1)=f(u_3)=a$. Denote by $f(u_2)=b$. If $f(v_2)=a$, then $v_3$ does not dominate any color class; if $f(v_2)=c$, since $v_1$ does not dominate color class $\{f^{-1}(a)\}$, it must be $f(v_n)=c$. However, $v_3$ does not dominate $\{f^{-1}(a)\}$ or $\{f^{-1}(c)\}$, a contradiction. $\square$

Lemma 13

For $n\equiv 1\bmod 4$, we have $\chi _d(P_2\square C_n)=2\lfloor n/4\rfloor +3$.

Proof

First suppose to the contrary that $\chi _d(P_2\Box C_n)\le 2\lfloor n/4\rfloor +2$.

Fact 1. There is no singleton color class.

Otherwise, by symmetry we assume that $\{u_n\}$ is a singleton color class, and when $n\ge 9$, $N[u_6]\cup N[v_8]\cup \cdots \cup N[v_{n-1}]$ consume at least $(n-5)/2$ colors, then $T_1$ only has three colors available, a contradiction.

Therefore, any vertex dominates the color class consisting of at least two of its neighbors. By Lemma 12 and the above fact, we may assume that $f(u_2)=1$, $f(v_2)=f(u_3)=2$ and $f(u_1)=3$. Since $u_2$ dominates color class $\{v_2,u_3\}$, color 2 cannot be used on other vertices any more. Furthermore, since when $n\ge 9$, $N[v_4]\cup N[u_6]\cup N[v_8]\cup \cdots \cup N[v_{n-1}]$ consume at least $(n-3)/2$ colors, we have $f(v_1)=f(u_n)=1$. However, by Fact 1 $v_2$ does not dominate any color class, a contradiction. So $\chi _d(P_2\square C_n)\ge 2\lfloor n/4\rfloor +3$.

On the other hand, we give a $(2\lfloor n/4\rfloor +3)$-dominator coloring for $P_2\square C_n$ as follows.

$$\begin{aligned} f(u_i)= & {} 2l+3 \quad {\text { for }}i=4l+1, l=0,1,\ldots ,\lfloor n/4\rfloor ,\\ f(u_i)= & {} 2 \quad {\text { for odd }}i{\text { except }}i=4l+1, l=0,1,\ldots ,\lfloor n/4\rfloor ,\\ f(u_i)= & {} 1 \quad {\text { for even }}i, 1\le i\le n,\\ f(v_j)= & {} 2l+4 \quad {\text { for }}j=4l+3, l=0,1,\ldots ,\lfloor n/4\rfloor -1,\\ f(v_j)= & {} 1 \quad {\text { for odd }}j, j\le n-2{\text { except }}j=4l+3, l=0,1,\ldots ,\lfloor n/4\rfloor -1,\\ f(v_j)= & {} 2 \quad {\text { for even }}j, 1\le j\le n-3{\text { or }}j=n,\\ f(v_{n-1})= & {} 2 \quad \lfloor n/4\rfloor +3. \end{aligned}$$

Hence $\chi _d(P_2\square C_n)\le 2\lfloor n/4\rfloor +3$, and then $\chi _d(P_2\square C_n)=2\lfloor n/4\rfloor +3$. $\square$

Lemma 14

For $n\equiv 2\bmod 4$, we have $\chi _d(P_2\square C_n)\ge 2\lfloor n/4\rfloor +4$.

Proof

Suppose to the contrary that $\chi _d(P_2\Box C_n)\le 2\lfloor n/4\rfloor +3$.

Fact 2. There is no singleton color class.

Otherwise, by symmetry we assume that $\{u_n\}$ is a singleton color class with $f(u_n)=2\lfloor n/4\rfloor +3$. By our observation, at least four colors appear on $T_1$, and when $n\ge 10$, $N[u_6]\cup N[v_8]\cup N[u_{10}]\cdots \cup N[v_{n-2}]$ consume at least $(n-6)/2$ colors. So $f(v_1)$, $f(v_n)$ and $f(u_{n-1})$ are reused colors. On the other hand, since $N[u_3]\cup N[v_5]\cup N[u_7]\cup \cdots \cup N[v_{n-1}]$ consume at least $(n-2)/2$ colors, we only have two colors to color vertices in set $\{u_1,v_1,v_2\}$. Without loss of generality, let $f(u_1)=f(v_2)=1$ and $f(v_1)=2$. Recall that $f(v_1)$ and $f(v_n)$ are reused colors, we have that $v_1$ dominates color class $\{f^{-1}(1)\}$. Assume that $N[v_5]\cup N[u_7]\cup \cdots \cup N[v_{n-1}]$ consumes colors $4,5,\cdots ,2\lfloor n/4\rfloor +2$, we only have colors 2 and 3 to color $N[u_3]$. It is easy to check that $v_2$ does not dominate any color class, a contradiction.

Therefore, any vertex dominates the color class consisting of at least two of its neighbors. By Lemma 12 and Fact 2, we may assume that $f(u_2)=1$, $f(v_2)=f(u_3)=2$ and $f(u_1)=3$. In this case, $v_1$ does not dominate color class $\{f^{-1}(2)\}$, so $f(v_n)=3$. When $n\ge 10$, $N[v_4]\cup N[u_6]\cup N[v_8]\cdots \cup N[v_{n-2}]$ consume at least $(n-4)/2$ colors, say they are $\{4,5,\ldots (n+2)/2\}$, then we only have two colors 1 and $2\lfloor n/4\rfloor +3$ to color vertices in $\{u_{n-1},u_n,v_1\}$. So $u_3$ dominates color class $\{f^{-1}(4)\}$. That is $f(v_3)=f(u_4)=4$. Since $u_4$ does not dominate color class $\{f^{-1}(2)\}$, we have $f(v_4)=f(u_5)=2\lfloor n/4\rfloor +3$. So, if $n=6$, then we have $f(v_5)=f(u_6)=f(v_1)=1$. However $u_5$ does not dominate any color class. If $n\ge 10$, then $u_4$ does not dominate any color class, since color $2\lfloor n/4\rfloor +3$ appears in $\{u_{n-1},u_n\}$, a contradiction. $\square$

Lemma 15

For $n\equiv 3\bmod 4$, we have $\chi _d(P_2\square C_n)=2\lfloor n/4\rfloor +4$.

Proof

First suppose to the contrary that $\chi _d(P_2\Box C_n)\le 2\lfloor n/4\rfloor +3$.

Fact 3. There is no singleton color class.

Assume to the contrary that $\{u_n\}$ is a singleton color class with $f(u_n)=2\lfloor n/4\rfloor +3$. By our observation, at least four colors appear on $T_1$, and when $n\ge 11$, $N[u_6]\cup N[v_8]\cup N[u_{10}]\cup \cdots \cup N[v_{n-3}]$ consume at least $(n-7)/2$ colors, so there is no new color on other vertices, then $f(v_n)$ is a reused color in $P_2\square C_n$. This implies that $N[v_{n-1}]\cup N[v_1]$ consume at least two colors. Since when $n\ge 11$, $N[u_3]\cup N[v_5]\cup N[u_7]\cup \cdots \cup N[v_{n-6}]$ consume at least $(n-7)/2$ colors, there are at most two colors to color vertices in vertex set $\{u_{n-5}, u_{n-4}, u_{n-3},u_{n-2}, v_{n-4}, v_{n-3}\}$. Without loss of generality, let $f(u_{n-5})=f(v_{n-4})=f(u_{n-3})=1$ and $f(u_{n-4})=f(v_{n-3})=f(u_{n-2})=2$. Since $v_{n-3}$ does not dominate color class $\{f^{-1}(1)\}$ or $\{f^{-1}(2)\}$, we have that $\{v_{n-2}\}$ is a single color class. Denote $T_{v_n}=\{v_n,v_1,v_2,v_3,u_1,u_2,u_3,u_4\}$. By our observation and symmetry, we know that there are at least four colors on $T_{v_n}$. Furthermore, when $n\ge 11$, $N[v_5]\cup N[u_7]\cup N[v_9]\cup \cdots \cup N[v_{n-2}]$ consume at least $(n-5)/2$ colors. Now there are $4+(n-5)/2+1=2\lfloor n/4\rfloor +4$ colors on $P_2\square C_n$, a contradiction.

Therefore, any vertex dominates the color class consisting of at least two of its neighbors. By Lemma 12 and Fact 3, we may assume that $f(u_2)=1$, $f(v_2)=f(u_3)=2$ and $f(u_1)=3$. In this case $v_1$ does not dominate color class $\{f^{-1}(2)\}$, so $f(v_n)=3$ and $v_1$ dominates color class $\{f^{-1}(3)\}$. Since $N[v_4]\cup N[u_6]\cup N[v_8]\cup \cdots \cup N[u_{n-1}]$ consume at least $(n-3)/2$ colors, say colors $4,5,\ldots ,(n+3)/2$, respectively, then we have $f(v_1)=1$ and each of $N[v_4], N[u_6], N[v_8],\ldots , N[u_{n-1}]$ consumes exactly one color. Now $u_3$ does not dominate color class $\{f^{-1}(1)\}$, so it dominates color class $\{v_3,u_4\}$. Since color class $\{f^{-1}(3)\}$ is dominated by $v_1$ and color class $\{f^{-1}(2)\}$ is dominated by $u_2$ , we have $f(v_3)=f(u_4)=4$. And since $N[v_4]$ consumes only one color, we have $f(v_4)\in \{1,2,3\}$, and so $f(v_4)=1$. However, in this case $v_2$ does not dominate any color class, a contradiction. So $\chi _d(P_2\square C_n)\ge 2\lfloor n/4\rfloor +4$

On the other hand, we give a $(2\lfloor n/4\rfloor +4)$-dominator coloring for $P_2\square C_n$ as follows.

$$\begin{aligned} f(u_i)= & {} 2l+3 \quad {\text { for }}i=4l+1, l=0,1,\ldots ,\lfloor n/4\rfloor ,\\ f(u_i)= & {} 2 \quad {\text { for odd }}i, i\le n-2{\text { except }}i=4l+1, l=0,1,\ldots ,\lfloor n/4\rfloor ,\\ f(u_i)= & {} 1 \quad {\text { for even }}i, 1\le i\le n-2,\\ f(u_{n-1})= & {} 2 \quad {\text { and }}f(u_{n})=1,\\ f(v_j)= & {} 2l+4 \quad {\text { for }}j=4l+3, l=0,1,\ldots ,\lfloor n/4\rfloor -1,\\ f(v_j)= & {} 1 \quad {\text { for odd }}j, j\le n-2{\text { except }}j=4l+3, l=0,1,\ldots ,\lfloor n/4\rfloor -1,\\ f(v_j)= & {} 2 \quad {\text { for even }}j, 1\le j\le n-3 or j=n,\\ f(v_{n-1})= & {} 2 \quad \lfloor n/4\rfloor +4. \end{aligned}$$

Hence $\chi _d(P_2\square C_n)\le 2\lfloor n/4\rfloor +4$, and then $\chi _d(P_2\square C_n)=2\lfloor n/4\rfloor +4$. $\square$

5 Conclusion

In [4] Gera proposed the question that for what graphs does $\chi _d(G)=\gamma (G)+\chi (G)$. By our results, we can see that for $G=P_2\square P_n$ with $n=3$ or $n\ge 5$ and $G=P_2\square C_n$ with even n the equality holds.