Total dominator chromatic number of graphs with specific construction

1. Introduction

In this paper, we are concerned with simple finite graphs, without direction, multiple, or weighted edges, and without self-loops. Let \(G=(V,E)\) be such a graph and \(\lambda \in \mathbb{N}\). A mapping \(f : V (G)\longrightarrow \{1, 2,...,\lambda\}\) is called a \(\lambda\)-proper coloring of \(G\) if \(f(u) \neq f(v)\) whenever the vertices \(u\) and \(v\) are adjacent in \(G\). A color class of this coloring is a set consisting of all those vertices assigned the same color. If \(f\) is a proper coloring of \(G\) with the coloring classes \(V_1, V_2,..., V_{\lambda}\) such that every vertex in \(V_i\) has color \(i\), then we write simply \(f = (V_1,V_2,...,V_{\lambda})\). The chromatic number \(\chi(G)\) of \(G\) is the minimum number of colors needed in a proper coloring of a graph. The concept of a graph coloring and chromatic number is very well-studied in graph theory. A dominator coloring of \(G\) is a proper coloring of \(G\) such that every vertex of \(G\) dominates all vertices of at least one color class (possibly its own class), i.e., every vertex of \(G\) is adjacent to all vertices of at least one color class. The dominator chromatic number \(\chi_d(G)\) of \(G\) is the minimum number of color classes in a dominator coloring of \(G\).

The concept of dominator coloring was introduced and studied by Gera, Horton and Rasmussen [1]. Let \(G\) be a graph with no isolated vertex, then the total dominator coloring (TD-coloring) is a proper coloring of \(G\) in which each vertex of the graph is adjacent to every vertex of some (other) color class [2]. The total dominator chromatic number (TDC-number), \(\chi_d^t(G)\) of \(G\) is the minimum number of color classes in a TD-coloring of \(G\). The TDC-number of a graph is related to its total domination number. A total dominating set of \(G\) is a set \(S\subseteq V(G)\) such that every vertex in \(V(G)\) is adjacent to at least one vertex in \(S\). The total domination number of \(G\), denoted by \(\gamma_t(G)\), is the minimum cardinality of a total dominating set of \(G\). A total dominating set of \(G\) of cardinality \(\gamma_t(G)\) is called a \(\gamma_t(G)\)-set.

The literature on the subject on total domination in graphs was surveyed and detailed in the book [3]. It is not hard to see that for every graph \(G\) with no isolated vertex, \(\gamma_t(G) \leq \chi_d^t(G)\). Computation of the TDC-number is NP-complete. The TDC-number of some operations of two graphs was studied in [2]. Also Henning in [4] established the lower and upper bounds on the TDC-number of a graph in terms of its total domination number. He showed that, for every graph \(G\) with no isolated vertex satisfies \(\gamma_t(G) \leq \chi_d^t (G)\leq \gamma_t(G) + \chi(G)\). The properties of TD-colorings in trees was studied in [4]. Trees \(T\) with \(\gamma_t(T) =\chi_d^t(T)\) was characterized in [4].

The join \(G = G_1 + G_2\) of two graph \(G_1\) and \(G_2\) with disjoint vertex sets \(V_1\) and \(V_2\) and edge sets \(E_1\) and \(E_2\) is the graph union \(G_1\cup G_2\) together with all the edges joining \(V_1\) and \(V_2\). For two graphs \(G = (V,E)\) and \(H=(W,F)\), the corona \(G\circ H\) is the graph arising from the disjoint union of \(G\) with \(| V |\) copies of \(H\), by adding edges between the \(i\)th vertex of \(G\) and all vertices of \(i\)th copy of \(H\).

In this paper, we continue the study of TD-colorings in graphs. We compute the TDC-number of some specific graphs in the Section 2. In Section 3, we study TD-chromatic number of corona and join of graphs.

Total dominator chromatic number of specific graphs

In this section, we consider the specific graphs and compute their TDC-numbers. First we need the TDC-number of path and cycle graph. Note that the value of TDC-number of paths and cycles which have computed in [5] are lower and upper bounds for \(\chi_d^t(P_n)\), \(\chi_d^t(C_n)\) and are not the exact value. For example by formula in [5], \(\chi_ d^t (P_{60})=40\) which is not true and the correct value is \(32\) which can obtain by the following theorem.

Theorem 1. If \(P_n\) is the path graph of order \(n\geq 8\), then \[ \chi_d^t(P_n)=\left\{ \begin{array}{ll} {\displaystyle 2k+2}& \quad\mbox{if \(n=4k\), }\\ {\displaystyle 2k+3}& \quad\mbox{if \(n=4k+1\),}\\ {\displaystyle 2k+4}& \quad\mbox{if \(n=4k+2\), \(n=4k+3\).}\\ \end{array} \right. \] Also \( \chi _ d^t (P_3)=2\), \( \chi _ d^t (P_4)= 3\), \(\chi _ d^t (P_5)= \chi _ d^t (P_6)=4\) and \( \chi _ d^t (P_7)=5\).

Proof. It is easy to show that \( \chi _ d^t (P_3)=2\), \( \chi _ d^t (P_4)= \chi _ d^t (P_5)=3\), \( \chi _ d^t (P_6)=4\) and \( \chi _ d^t (P_7)=5\). Now let \(n\geq 8\). First we show that for each four consecutive vertices we have to use at least two new colors. Consider Figure 1. We have two cases. If we give an old color to \(v_{i+1}\), then we need to give a new color to \(v_{i+2}\) and \(v_{i+3}\) to have a TD-coloring. Also if we give a new color to \(v_{i+1}\), then we have to give a new color to \(v_{i+2}\) or \(v_{i}\) to have a TD-coloring. So we need at least two new colors in every four consecutive vertices.
Suppose that \(n=4k\), for some \(k\in \mathbb{N}\). We give a TD-coloring for the path \(P_{4k}\) which use only two new colors in every four consecutive vertices. Define a function \(f_0\) on the vertices of \(P_{4k}\), i.e., \(V(P_{4k})\) such that for any vertex \(v_i\), \[f_0(v_i)=\left\{ \begin{array}{ll} {\displaystyle 1} & \quad\mbox{if \(i=1+4k\),}\\ {\displaystyle 2} & \quad\mbox{if \(i=4k\),} \end{array} \right.\] and for any \(v_i\) , \(i \neq 4k\) and \(i\neq 4k+1\), \(f_0(v_i)\) is a new number. Then \(f_0\) is a TD-coloring of \(P_{4k}\) with the minimum number \(2k+2\).

If \(n=4k+1\), for some \(k\in \mathbb{N}\), then first color the \(4k-4\) vertices using \(f_0\). Now for the rest of vertices define \(f_1(v_{4k-3})=1\), \(f_1(v_{4k-2})=2k+1\), \(f_1(v_{4k-1})=2k+2\), \(f_1(v_{4k})=2k+3\) and \(f_1(v_{4k+1})=2\). Since for every five consecutive vertices we have to use at least three new colors, so \(f_1\) is a TD-coloring of \(P_{4k+1}\) with the minimum number \(2k+3\).
If \(n=4k+2\), for some \(k\in \mathbb{N}\), then first color the \(4k-4\) vertices using \(f_0\). Now for the rest of vertices define \(f_2(v_{4k-3})=1\), \(f_2(v_{4k-2})=2k+1\), \(f_2(v_{4k-1})=2k+2\), \(f_2(v_{4k})=2k+3\), \(f_2(v_{4k+1})=2k+4\) and \(f_2(v_{4k+2})=2\). Since for every six consecutive vertices we have to use at least four new colors, so \(f_2\) is a TD-coloring of \(P_{4k+2}\) with the minimum number \(2k+4\).
If \(n=4k+3\), for some \(k\in \mathbb{N}\), then first color the \(4k-4\) vertices using \(f_0\). Now for the rest of vertices define \(f_3(v_{4k-3})=1\), \(f_3(v_{4k-2})=2k+1\), \(f_3(v_{4k-1})=2k+2\), \(f_3(v_{4k})=2\), \(f_3(v_{4k+1})=2k+3\), \(f_3(v_{4k+2})=2k+4\) and \(f_3(v_{4k+2})=2\). Then \(f_3\) is a TD-coloring of \(P_{4k+2}\) with the minimum number \(2k+4\). Therefore we have the result.

Theorem 2. Let \(C_n\) be the cycle graph of order \(n\geq 8\). Then \[ \chi _ d^t (C_n)=\left\{ \begin{array}{ll} {\displaystyle 2k+2} & \quad\mbox{if \(n=4k\),}\\ {\displaystyle 2k+3}& \quad\mbox{if \(n=4k+1\),}\\ {\displaystyle 2k+4}& \quad\mbox{if \(n=4k+2\), \(n=4k+3\).} \end{array} \right. \] Also \( \chi _ d^t (C_3)=3\), \( \chi _ d^t (C_4)=2\), \( \chi _ d^t (C_5)= \chi _ d^t (P_6)=4\) and \( \chi _ d^t (C_7)=5\).

Proof. Observe that \(\chi_d^t(C_3)=3\), \( \chi_d^t (C_4)=2\), \( \chi_d^t (C_5)= \chi_d^t (C_6)=4\) and \( \chi_d^t (C_7)=5\). Now let \(n\geq 8\). It is sufficient to give a TD-coloring to the \(P_n\) as we see in the proof of the Theorem 1, then we add an edge between vertices \(v_1\) and \(v_n\). Then we have a TD-coloring for \(C_n\) and the result follows.

From Theorems 1 and 2, we have the following corollary.

Corollary 1. For every \(n\geq6\), \(\chi _ d^t (P_n)=\chi _ d^t (C_n)\).

Here we consider the ladder graph. We need the definition of Cartesian product of two graphs. Given any two graphs \(G\) and \(H\), we define the Cartesian product, denoted \(G\Box H\), to be the graph with vertex set \(V(G)\times V(H)\) and edges between two vertices \((u_1, v_1)\) and \((u_2,v_2)\) if and only if either \(u_1 = u_2\) and \(v_1v_2 \in E(H)\) or \(u_1u_2 \in E(G)\) and \(v_1 = v_2\).
Let \(n\geq 2\) be a natural number. The \(n\)-ladder graph can be defined as \(P_2\Box P_n\) and denoted by \(L_n\). Figure 2 shows a TD-coloring of ladder graphs.

Theorem 3. For every \(n\geq 2\), \[ \chi_d^t(L_n)=\left\{ \begin{array}{lr} {\displaystyle n+1}&\quad\mbox{if \(n\) is odd,}\\ {\displaystyle n}& \quad\mbox{if \(n\) is even.} \end{array} \right. \]

Proof. Let \(x_{ij}\) be a vertex of ladder graph in \(i\)-th row and \(j\)-th column (\(1\leq i\leq 2\) and \(1\leq j\leq n\)). If \(n=2k+1\) for some \(k\in \mathbb{N}\), then we color the vertex \(x_{1j}\) with color \(j\) and for vertices \(x_{2j}\) we assign the color \(2j+2\) for \(x_{2(2j+1)}\) and color \(2j-1\) for vertex \(x_{2(2j)}\) (Figure 2). This coloring gives a TD-coloring for \(L_n\) and this method warranty the least number of used colors. So \(\chi_d^t(L_{2k+1})=2k+2\). With similar argument we have the result for even \(n\).

I am raw html block.
Click edit button to Here, we generalize the ladder graph \(P_2\Box P_n\) to grid graphs \(P_n\Box P_m\). The following theorem gives the TDC-number of grid graphs:

Theorem 4. Let \(m,n\geq 2\). The TDC-number of grid graphs \(P_n\Box P_m\) is, \[ \chi_d^t(P_n\Box P_m)=\left\{ \begin{array}{lr} {\displaystyle k \chi_d^t(P_n\Box P_2)=k\chi_d^t(L_n)}&\quad\mbox{if \(m=2k\) and \(n=2s\),}\\ {\displaystyle k\chi_d^t(L_n)+\chi_d^t(P_n)}& \quad\mbox{if \(m=2k+1\) and \(n=2s\),}\\ {\displaystyle s\chi_d^t(L_m)+\chi_d^t(P_m)}& \quad\mbox{if \(m=2k\) and \(n=2s+1\),}\\ {\displaystyle \chi_d^t(P_{n-1}\Box P_{m-1})+\chi_d^t(P_{m+n-1})}& \quad\mbox{if \(m=2k+1\) and \(n=2s+1\).} \end{array} \right. \]

Proof. We prove two first cases. The proof of another cases are similar. Suppose that \(m=2k\) and \(n=2s\), for some \(k\) and \(s\). We use induction on \(m\).
Case 1. If \(m=2\) and \(n=2s\), then we have a ladder and the result follows from Theorem 3. For \(m=2\), as you see in Figure 3, we have two \(L_n\) as subgraphs of \(4\times n\) grid graph. Since in TD-coloring of \(4\times n\) grid graph, we can not use the colors of vertices in the first ladder, for the second ladder, so we need \(2\chi_d^t(L_n)\) colors. It is easy to see that we cannot use less colors. Since in the \(P_n\Box P_{2k}\), there are exactly \(k\) ladder \(L_n\) as subgraphs, we have the result by induction hypothesis.this html

Case 2. Now suppose that \(n=2s\) and \(m=2k+1\). First for TD-coloring of \(P_n\Box P_{2k}\), by Case 1, we need \(k\chi_d^t(L_n)\) colors. It remains to color a path \(P_n\). Therefore we need \(k\chi_d^t(L_n)+\chi_d^t(P_n)\) colors to obtain a TD-coloring of \(P_n\Box P_m\). By the same argument in the proof of Theorem 3 we conclude that less colors cannot used for TD-coloring of this graph.

Now we consider graphs with specific construction. Let \(G\) be a connected graph constructed from pairwise disjoint connected graphs \(G_1,...,G_k\) as follows: Select a vertex of \(G_1\), a vertex of \(G_2\), and identify these two vertices. Then continue in this manner inductively. Note that the graph \(G\) constructed in this way has a tree-like structure, the \(G_i\)'s being its building stones (see Figure 4). Usually say that \(G\) is obtained by point-attaching from \(G_1,..., G_k\) and that \(G_i\)'s are the primary subgraphs of \(G\). A particular case of this construction is the decomposition of a connected graph into blocks (see [6]).

As an example consider the graph \(Q(m, n)\) constructed in the following manner: consider the graph \(K_m\) and \(m\) copies of \(K_n\) (see [6]). By definition, the graph \(Q(m, n)\) is obtained by identifying each vertex of \(K_m\) with a vertex of a unique \(K_n\), see Figure 4. The following theorem gives the TDC-number of \(Q(m,n\)):

Theorem 5. Let \(m,n\geq 2\) be integers. For the graph \(Q(m,n)\) we have: $$\chi_d^t(Q(m,n))=m+n-1.$$

Proof. We need colors \(1,2,\ldots,m\) to color the complete graph \(K_m\). Now for the rest of vertices of \(Q(m,n)\), we use colors \(m+1,m+2,\ldots,m+n-1\) in each \(K_n\). This gives a TD-coloring for \(Q(m,n)\). We shall show that we are not able to have TD-coloring with less colors. Suppose that we omit one color class between numbers \(m+1,m+2,\ldots,m+n-1\). Consider one copy of \(K_n\) and simply call it \(G_1\) and call the vertex which has no color as \(v\). We have to use one color from the numbers \(1,2,\ldots,m\) to color \(v\). Suppose that this color is \(i\), where \(1\leq i\leq m\). Then there is another copy of \(K_n\), say \(G_2\) which has a vertex with color \(i\) (point attached vertex). Also there is \(w \in V(G_2)\) such that has no color. We cannot color \(w\) with \(m+1,m+2,\ldots,m+n-1\). Since \(w\) is not adjacent to \(v\), so it cannot get an arbitrary color from \(1,2,\ldots,m\). Therefore we have to change the color of a vertex \(s\in V(G_2)-\{w\}\) to \(j \in \{1,2,\ldots,m\}\). But \(w\) is not adjacent to the vertex with color \(j\) in \(K_m\). So we cannot give the vertex \(w\) any color. By the same argument we cannot omit two color classes and so on. Therefore \(\chi_d^t(Q(m,n))=m+n-1\).

Let to consider a special cases of point attaching of \(k\) graphs. Let \(G_1,G_2,..., G_k\) be a finite sequence of pairwise disjoint connected graphs and let \(x_i, y_i\in V (G_i)\). The link \(G\) of the graphs \(\{G_i\}_{i=1}^k\) with respect to the vertices \(\{x_i, y_i\}_{i=1}^k\) is obtained by adding an edge which connect the vertex \(y_i\) of \(G_i\) with the vertex \(x_{i+1}\) of \(G_{i+1}\) for all \(i = 1, 2,..., k-1\), see Figure 5, [6].

Here we shall study the total dominator coloring of families of graphs which obtained by point attaching from \(G_1,...,G_k\).

Theorem 6. Let \(G\) be a graph obtained by point attaching from \(G_1,...,G_k\). Then $$\chi_d^t(G)\leq\chi_d^t(G_1)+\chi_d^t(G_2)+\ldots + \chi_d^t(G_n).$$

Proof. Since we can use numbers \(1,2,\ldots, \chi_d^t(G_1)\) for \(G_1\) and use numbers \( \chi_d^t(G_1)+1, \chi_d^t(G_1)+2,\ldots, \chi_d^t(G_1)+ \chi_d^t(G_2)\) for \(G_2\) and continue this process, then we have a TD-coloring . Therefore we have the result.

We shall show that the upper bound in Theorem 6 is sharp. For this reason, we consider a special kind of link graph has shown in Figure 5.

Theorem 7. For the graph \(L_{6,2,n}\) in Figure 5 we have: $$\chi_d^t(L_{6,2,n})=4n.$$

Proof. We color the vertices of \(L_{6,2,n}\) with numbers \(1,2,3,...,4n\), as shown in the Figure 5. Observe that, we need \(4n\) color for TD-coloring. We shall show that we are not able to have TD-coloring with less colors. Note that \(L_{6,2,1}\) is \(C_6\) and \(\chi_d^t(C_6)=4\). Now we consider \(L_{6,2,2}\). Two kinds of coloring of \(L_{6,2,2}\) has shown in Figure 6.

We show that \(\chi_d^t(L_{6,2,2})=8\). If we want to omit one color class and use another color, then we cannot have a TD-coloring. For example if we delete color \(5\), then

• (i) We cannot use color \(1\), since a vertex with color \(2\) exists which is not adjacent to the mentioned vertecis.
• (ii) We cannot use colors \(6,7\) (or color \(2\) in the right figure), since the coloring is proper.
• (iii) We cannot use color \(3\) or \(4\), because the vertices with these colors are not adjacent with the mentioned vertices.
• (iv) We cannot use color \(8\) because the vertex with color \(6\) is not adjacent to the vertex with color \(8\).

Argument about the rest of the colors is the same. So we have \(\chi_d^t(L_{6,2,2})=8\). Using this inductively method have the result for \(L_{6,2,n}\).

Here we investigate the relation of TDC-number of a graph \(G\) with TDC-number of \(G-e\), where \(e\in E(G)\):

Theorem 8. If \(G\) is a connected graph, and \(e=vw\in E(G)\) is not a bridge, then $$\chi_d^t(G-e)\leq \chi_d^t(G)+2 .$$

Proof. Suppose that the vertex \(v\) has color \(i\) and the vertex \(w\) has color \(j\). We have the following cases:
Case 1. The vertex \(v\) does not use the color class \(j\) and the vertex \(w\) does not use the color class \(i\) in the TD-coloring of \(G\). So the TD-coloring of \(G\) gives a TD-coloring of \(G-e\). Therefore \(\chi_d^t(G-e)\leq \chi_d^t(G)\). In this case \(\chi_d^t(G-e)=\chi_d^t(G)\).
Case 2. The vertex \(v\) uses the color class \(j\) but the vertex \(w\) does not use the color class \(i\) in the TD-coloring of \(G\). Since the vertex \(v\) used the color class \(j\) for The TD-coloring then we have two cases:

• (i) If the vertex \(v\) has some adjacent vertices which have color \(j\), then we give the new color \(l\) to all of these vertices and this coloring is a TD-coloring for \(G-e\).
• (ii) If any other vertex does not have color \(j\), since \(G-e\) is a connected graph, then there exists a vertex \(s\) which is adjacent to \(v\). Now we give the vertex \(s\) a new color \(l\) and this coloring is a TD-coloring for \(G-e\).

So for the Case 2, we have \(\chi_d^t(G-e)= \chi_d^t(G)+1\).
Case 3. The vertex \(v\) uses the color class \(j\) and the vertex \(w\) uses the color class \(i\) in the TD-coloring of \(G\). We have three cases:

• (i) There are some vertices which are adjacent to vertex \(v\) and have color \(j\). Then we color all of them with color \(l\), and there are some vertices which are adjacent to the vertex \(w\) and have color \(i\). We color all of them with color \(k\). So this is a TD-coloring for \(G-e\).
• (ii) Any other vertex does not have color \(j\). Then we do the same as Case 2 (ii) and there are some vertices which are adjacent to the vertex \(w\) and have color \(i\). Then we do the same as Case 3 (i).
• (iii) Any other vertex does not have colors \(i\) and \(j\). Then we do the same as Case 2 (ii) and use two new colors \(l\) and \(k\).

So we have \(\chi_d^t(G-e)\leq \chi_d^t(G)+2\).

3. TDC-number of corona and join of graphs

In this section, we study the TDC-number of corona and join of two graphs. In the following theorem, we consider graphs of the form \(G\circ H\) and study their TDC-numbers:

Theorem 9.

• (i) For every connected graph \(G\), \(\chi_d^t(G\circ K_1)=|V(G)|+1\),
• (ii) For every two connected graphs \(G\) and \(H\), $$\chi_d^t(G\circ H)\leq \chi_d^t(G)+|V(G)|\chi_d^t(H).$$
• (iii) For every two connected graphs \(G\) and \(H\), $$\chi_d^t(G\circ H)\leq |V(G)|+|V(H)|.$$

Proof.

• (i) We color all vertices of graph \(G\) with numbers \(\{1,2,...,|V(G)|\}\) and all pendant vertices with another color, say, \(|V(G)|+1\). It is easy to check that we are not able to have TD-color of \(G\circ K_1\) with less color. Therefore we have the result.
• (ii) For TD-coloring of \(G\) and \(H\), we need \(\chi_d^t(G)\) and \(\chi_d^t(H)\) colors, respectively. We observe that if we use \(\chi_d^t(G)+|V(G)|\chi_d^t(H)\) colors, then we have a TD-coloring of \(G\circ H\). So \(\chi_d^t(G\circ H)\leq \chi_d^t(G)+|V(G)|\chi_d^t(H)\).
• (iii) We color the vertices of \(G\), by \(|V(G)|\) colors and for every copy of \(H\), we use \(|V(H)|\) another colors. We observe that this coloring gives a TD-coloring of \(G\circ H\). So \(\chi_d^t(G\circ H)\leq |V(G)|+|V(H)|.\)

Remark 1 The upper bound for \(\chi_d^t(G\circ H)\) in Theorem 9(iii) is a sharp bound. As examples, for the graph \(C_4\circ K_2\) and \(K_2\circ K_3\) we have the equality (Figure 7).

Here, we state and prove a formula for the TDC-number of join of two graphs:

Theorem 10. Let \(G\) and \(H\) be two connected graphs, \(\vert V(G) \vert\geq 2 \) and \(\vert V(H) \vert\geq 2\) , then $$\chi_d^t(G+H)=\chi_d^t(G)+\chi_d^t(H).$$

Proof. For the TD-coloring of \(G+H\), the colors of vertices of \(G\) cannot be used for the coloring of vertices of \(H\), and the colors of the vertices of \(H\) cannot use for coloring of the vertices of \(G\), so $$\chi_d^t(G+H)\geq \chi_d^t(G)+\chi_d^t(H).$$ Now, it suffices to consider the coloring of \(G\) and the coloring of \(H\) in the TD-coloring of \(G+H\). Therefore, we have the result.

Acknowledgments

The authors would like to express their gratitude to the referees for their careful reading.

Author Contributions

All authors contributed equally to the writing of this paper. All authors read and approved the final manuscript.

Conflict of Interests

The authors declare no conflict of interest.