Total dominator total chromatic numbers of some graphs

Vusuqi, Leila; Kazemi,  Adel P.; Kazemnejad, Farshad

doi:10.61091/um121-07

Abstract

1. Introduction
2. Wheels
3. Complete bipartite graphs
4. Complete graphs

References

Utilitas Mathematica

Volume 121
Pages: 91-103

Research article

Total dominator total chromatic numbers of some graphs

^¹, ^¹, ^²

¹Faculty of Mathematical Sciences, University of Mohaghegh Ardabili P.O.\ Box 5619911367, Ardabil, Iran

²Department of Mathematics, Faculty of Basic Sciences, Ilam University P.O.Box 69315-516, Ilam, Iran

Received: 29/10/2024
Accepted: 14/12/2024
Published: 31/12/2024

Copyright Link
License

Abstract

Total dominator total coloring of a graph is a total coloring of the graph such that each object of the graph is adjacent or incident to every object of some color class. The minimum namber of the color classes of a total dominator total coloring of a graph is called the total dominator total chromatic number of the graph. Here, we will find the total dominator chromatic numbers of wheels, complete bipartite graphs and complete graphs.

Keywords: Total dominator total coloring, Total dominator total chromatic number, Total domination number, Total mixed domination number, Total graph

1. Introduction

Here, in a simple graph $G = (V, E)$ , while $d e g_{G} (v)$ , $N_{G} (v)$ and $N_{G} [v]$ denote respectively the degree, open and closed neighborhoods of a vertex $v \in V$ , the minimum degree, maximum degree and independence number of $G$ are denoted by $δ = δ (G)$ , $Δ = Δ (G)$ and $α = α (G)$ , respectively. A maximum independent set is an independent set of cardinality $α (G)$ . Also a mixed independent set of $G$ is a subset of $V \cup E$ , no two objects of which are adjacent or incident, and a maximum mixed independent set is a mixed independent set of the largest cardinality in $G$ . This cardinality is called the mixed independence number of $G$ , and is denoted by $α_{m i x} (G)$ . Two isomorphic graphs $G$ and $H$ are shown by $G ≅ H$ . We write $K_{n}$ , $C_{n}$ and $P_{n}$ for a complete graph, a cycle and a path of order $n$ , respectively, while $W_{n}$ , $K_{m, n}$ and $G [S]$ denote a wheel of order $n + 1$ , a complete bipartite graph of order $m + n$ and the induced subgraph of $G$ by a vertex set $S$ , respectively. Also for any positive integer $k$ , we use $[k]$ to denote the set ${1, 2, \dots, k}$ .

The Cartesian product $G H$ of two graphs $G$ and $H$ is a graph with $V (G) \times V (H)$ and two vertices $(g_{1}, h_{1})$ and $(g_{2}, h_{2})$ are adjacent if and only if either $g_{1} = g_{2}$ and $(h_{1}, h_{2}) \in E (H)$ , or $h_{1} = h_{2}$ and $(g_{1}, g_{2}) \in E (G)$ .

While the line graph $L (G)$ of $G = (V, E)$ is a graph with the vertex set $E$ in which two vertices are adjacent when they are incident in $G$ , the total graph $T (G)$ of a graph $G$ is the graph whose vertex set is $V \cup E$ and two vertices are adjacent whenever they are either adjacent or incident in $G$ . It is obvious that if $G$ has order $n$ and size $m$ , then $T (G)$ has order $n + m$ and size $3 m + | E (L (G)) |$ , and also $T (G)$ contains both $G$ and $L (G)$ as two induced subgraphs and it is the largest graph formed by adjacent and incidence relation between graph elements.

In this paper, by assumption $V = {v_{1}, v_{2}, \dots, v_{n}}$ , we use the notations $V (T (G)) = V \cup E$ where $E = {e_{i j} | v_{i} v_{j} \in E}$ , and $E (T (G)) = {v_{i} e_{i j}, v_{j} e_{i j} | v_{i} v_{j} \in E} \cup E \cup E (L (G))$ . Obviousely $d e g_{T (G)} (v_{i}) = 2 d e g_{G} (v_{i})$ and $d e g_{T (G)} (e_{i j}) = d e g_{G} (v_{i}) + d e g_{G} (v_{j})$ . So if $G$ is $k$ -regular, then $T (G)$ is $2 k$ -regular. Also $α_{m i x} (G) = α (T (G))$ . For an example, a graph $G$ and its total graph are shown in Figure 1.

Figure 1 The illustration of $G$ (left) and $T (G)$ (right)

1.1. Total mixed dominating set

Total domination in graphs is now well studied in graph theory and the literature on this subject has been surveyed and detailed in the book [2]. A vertex subset of a graph with this property that every vertex of the graph is adjacent to some vertex of the set is called a total dominating set, briefly TD-set, of the graph, and the minimum cardinality of a TD-set of a graph $G$ is called the total domination number $γ_{t} (G)$ of $G$ . In [8] the authors has defined total mixed dominating set of a graph as follows.

Definition 1.1. [8] A subset $S \subseteq V \cup E$ of a graph $G$ is called a total mixed dominating set, briefly TMD-set, of $G$ if each object of $V \cup E$ is either adjacent or incident to an object of $S$ , and the total mixed domination number

γ_{t m} (G)

of $G$ is the minimum cardinality of a TMD-set.

A min-TD-set/min-TMD-set of $G$ denotes a TD-set/TMD-set of $G$ with minimum cardinality. Also we agree that a vertex $v$ dominates an edge $e$ or an edge $e$ dominates a vertex $v$ mean $v \in e$ . Similarly, we agree that an edge dominates another edge means they have a common vertex.

1.2. TD-coloring and TDT-coloring of a graph

Graph coloring is used as a model for a vast number of practical problems involving allocation of scarce resources (e.g., scheduling problems), and has played a key role in the development of graph theory and, more generally, discrete mathematics and combinatorial optimization. Graph colorability is NP-complete in the general case, although the problem is solvable in polynomial time for many classes. true cm

If a function $f : V \to [k]$ from the vertex of a graph $G$ to a $k$ -set $[k]$ of colors such that any two adjacent vertices have different colors, then $f$ is called a proper $k$ -coloring of $G$ . The minimum number $k$ of colors needed in a proper coloring of a graph $G$ is called the chromatic number of $G$ and denoted by $χ (G)$ . In a proper coloring of a graph, a set consisting of all those vertices assigned the same color is called a color class. Trivially every color class contains at most $α (G)$ vertices. For simply, we denote a proper coloring $f$ of a graph with $ℓ$ color classes $V_{1}$ , $\dots$ , $V_{ℓ}$ by $f = (V_{1}, V_{2}, \dots, V_{ℓ})$ .

In a simlar way, a total coloring of $G$ assigns a color to each vertex and to each edge so that colored objects have different colors when they are adjacent or incident, and the minimum number of colors needed in a total coloring of a graph is called the total chromatic number $χ_{T} (G)$ of $G$ .

Motivated by the relation between coloring and total dominating, the concept of total dominator coloring in graphs introduced in [5] by Kazemi, and extended in [1,3,4,5,6,10,7,9,11].

Definition 1.2. [5] A total dominator coloring, briefly TD-coloring, of a graph $G$ with a possitive minimum degree is a proper coloring of $G$ in which each vertex of the graph is adjacent to every vertex of some color class. The total dominator chromatic number $χ_{d}^{t} (G)$ of $G$ is the minimum number of color classes in a TD-coloring of $G$ .

In [9], the authors initiated studying of a new concept called total dominator total coloring in graphs which is obtained from the concept of total dominator coloring of a graph by replacing total coloring of a graph instead of coloring of it.

Definition 1.3. [9] A total dominator total coloring, briefly TDT-coloring, of a graph $G$ with a possitive minimum degree is a total coloring of $G$ in which each object of the graph is adjacent or incident to every object of some color class. The total dominator total chromatic number $χ_{d}^{t t} (G)$ of $G$ is the minimum number of color classes in a TDT-coloring of $G$ .

For any TD-coloring (TDT-coloring) $f = (V_{1}, V_{2}, \dots, V_{ℓ})$ of a graph $G$ , a vertex (an object) $v$ is called a common neighbor of $V_{i}$ or we say $V_{i}$ totally dominates $v$ , and we write $v ≻_{t} V_{i}$ , if vertex (object) $v$ is adjacent (adjacent or incident) to every vertex (object) in $V_{i}$ . Otherwise we write $v ⊁_{t} V_{i}$ . Also $v$ is called a private neighbor of $V_{i}$ with respect to $f$ if $v ≻_{t} V_{i}$ and $v ⊁_{t} V_{j}$ for all $j \neq i$ . The set of all common neighbors of $V_{i}$ with respect to $f$ is called the common neighborhood of $V_{i}$ in $G$ and denoted by $C N_{G, f} (V_{i})$ or simply by $C N (V_{i})$ . Also every TD-coloring or TDT-coloring of $G$ with $χ_{d}^{t} (G)$ or $χ_{d}^{t t} (G)$ colors is called respectively a min-TD-coloring or a min-TDT-coloring.

Also for any TD-coloring $(V_{1}, V_{2}, \dots, V_{ℓ})$ and any TDT-coloring $(W_{1}, W_{2}, \dots, W_{ℓ})$ of a graph $G = (V, E)$ , we have $\begin{matrix} (1) & ⋃_{i = 1}^{ℓ} C N (V_{i}) = V and ⋃_{i = 1}^{ℓ} C N (W_{i}) = V \cup E . \end{matrix}$

1.3. Goal of the paper

In [9], the authors initiated to study the TDT-coloring of a graph and found some useful results, and presented some problems such as finding the total dominator total chromatic numbers of wheels, complete bipartite graphs and complete graphs, that we consider them here. For that we use the following two theorems that state the total mixed domination and total dominator total chromatic numbers of a graph are respectively the total domination and total dominator chromatic numbers of the total of the graph.

Theorem 1.4. [8] For any graph

G

without isolate vertex,

γ_{t m} (G) = γ_{t} (T (G))

Theorem 1.5. [9] For any graph

G

without isolate vertex,

χ_{d}^{t t} (G) = χ_{d}^{t} (T (G))

2. Wheels

Here, we calculate the total dominator total chromatic number of a wheel. First we calculate the mixed indepence number of a wheel, and state some facts on the structure of a minimal TD-coloring of the total of a wheel. But before that, we recall the following propositions which are needed in its proof.

Proposition 2.1. [5] For any connected graph

G

with

δ (G) \geq 1

χ_{d}^{t} (G) \leq γ_{t} (G) + min_{S} χ (G [V (G) - S]),

where

S \subseteq V (G)

is a min-TD-set of

G

. And so

χ_{d}^{t} (G) \leq γ_{t} (G) + χ (G)

Proposition 2.2. [8] For any wheel

W_{n}

of order

n + 1 \geq 4

γ_{t m} (W_{n}) = ⌈ \frac{n}{2} ⌉ + 1

Proposition 2.3. [7] For any integer

n \geq 3

, if

G

is a cycle or a path of order

n

α_{m i x} (G) = ⌊ \frac{2 n}{3} ⌋ + ϵ

in which

ϵ = 1

when

G

is the path

P_{n}

of order

n \equiv 1 (\mod 3)

, and

ϵ = 0

otherwise.

Lemma 2.4 For any wheel $W_{n}$ of order $n + 1 \geq 4$ , $α_{m i x} (W_{n}) = ⌈ \frac{2 n}{3} ⌉$ .

Proof. Let $W_{n} = (V, E)$ be a wheel of order $n + 1 \geq 4$ where $V = {v_{i} | 0 \leq i \leq n}$ and $E = {v_{0} v_{i}, v_{i} v_{i + 1} | 1 \leq i \leq n}$ . Then $V (T (W_{n})) = V \cup E$ when $E = {e_{0 i}, e_{i (i + 1)} | 1 \leq i \leq n}$ . Let $S$ be an independent set of $T (W_{n})$ . Since the subgraph induced by ${e_{0 i} | 1 \leq i \leq n} \cup {v_{0}}$ is a complete graph, we have $| S \cap ({e_{0 i} | 1 \leq i \leq n} \cup {v_{0}}) | \leq 1$ . If $| S \cap ({e_{0 i} | 1 \leq i \leq n} \cup {v_{0}}) | = 0$ , then $S \subseteq {v_{i}, e_{i (i + 1)} | 1 \leq i \leq n}$ , and since the subgraph induced by ${v_{i}, e_{i (i + 1)} | 1 \leq i \leq n}$ is isomorphic to $T (C_{n})$ , Proposition 2.3 implies $| S | \leq ⌊ \frac{2 n}{3} ⌋$ . If also $v_{0} \in S$ , then $S \subseteq {e_{i (i + 1)} | 1 \leq i \leq n}$ , and since the subgraph induced by ${e_{i (i + 1)} | 1 \leq i \leq n}$ is isomorphic to $C_{n}$ , we have $| S | \leq α (C_{n}) + 1 = ⌊ \frac{n}{2} ⌋ + 1$ . Finally if $e_{0 i} \in S$ for some $1 \leq i \leq n$ , then $S \subseteq V \cup E - N_{T (W_{n})} (e_{0 i})$ , and since the subgraph induced by $V \cup E - N_{T (W_{n})} (e_{0 i})$ is isomorphic to $T (P_{n - 1})$ , Proposition 2.3 implies $| S | \leq ⌈ \frac{2 n}{3} ⌉$ . Therefore $α_{m i x} (W_{n}) = α (T (W_{n})) = max {⌊ \frac{2 n}{3} ⌋, ⌊ \frac{n}{2} ⌋ + 1, ⌈ \frac{2 n}{3} ⌉} = ⌈ \frac{2 n}{3} ⌉$ .

Fact 2.5. Let $f = (V_{1}, V_{2}, \dots, V_{ℓ})$ be a minimal TD-coloring of $T (W_{n})$ where $n \geq 3$ and $| V_{1} | \geq \dots \geq | V_{ℓ} |$ , and let $B_{i} = {V_{k} | e_{i (i + 1)} ≻_{t} V_{k} and | V_{k} | = i for some e_{i (i + 1)} \in E_{1}}$ and $b_{i} = | B_{i} |$ for $1 \leq i \leq ⌈ \frac{2 n}{3} ⌉$ . Then the following facts are hold.

$\sum_{i = 1}^{ℓ} | V_{i} | = 3 n + 1$ , by $| V | = \sum_{i = 1}^{ℓ} | V_{i} |$ and $3 n + 1 \leq ℓ ⌈ \frac{2 n}{3} ⌉$ .
For any $v \in E_{0} \cup E_{1}$ , if $v ≻_{t} V_{k}$ for some $1 \leq k \leq ℓ$ , then $| V_{k} | \leq 2$ .
If $e_{i (i + 1)} ≻_{t} V_{k}$ for some $e_{i (i + 1)} \in E_{1}$ and some $1 \leq k \leq ℓ$ and $| V_{k} | = 2$ , then $C N (V_{k}) \cap E_{1} = {e_{i (i + 1)}}$ .
If $e_{i (i + 1)} ≻_{t} V_{k}$ for some $1 \leq k \leq ℓ$ and $| V_{k} | = 1$ , then $| C N (V_{k}) \cap E_{1} | = 2$ .
$n \leq 2 b_{1} + b_{2} \leq ℓ$ (by 3 and 4).
For $1 \leq i \leq n$ , if $v_{i} ≻_{t} V_{k}$ for some $1 \leq k \leq ℓ$ , then $| V_{k} | \leq 3$ .
For $1 \leq i \leq n$ , if $v_{i} ≻_{t} V_{k}$ for some $1 \leq k \leq ℓ$ and $| V_{k} | = 3$ , then $C N (V_{k}) = {v_{0}}$ .
If $v_{0} ≻_{t} V_{k}$ for some $1 \leq k \leq ℓ$ , then $| V_{k} | \leq ⌊ \frac{n}{2} ⌋ + 1$ .

Proposition 2.6. For any wheel $W_{n}$ of order $n + 1 \geq 4$ , $χ_{d}^{t t} (W_{n}) = {\begin{cases} n + 2 & if 3 \leq n \leq 7, \\ n + 1 & if n \geq 8. \end{cases}$

Proof. Let $W_{n} = (V, E)$ be a wheel of order $n + 1 \geq 4$ where $V = {v_{i} | 0 \leq i \leq n}$ and $E = {v_{0} v_{i}, v_{i} v_{i + 1} | 1 \leq i \leq n}$ . Then $V (T (W_{n})) = V \cup E_{0} \cup E_{1}$ when $E_{0} = {e_{0 i} | 1 \leq i \leq n}$ and $E_{1} = {e_{i (i + 1)} | 1 \leq i \leq n}$ . Let $f = (V_{1}, \dots, V_{ℓ})$ be a minimal TD-coloring of $T (W_{n})$ where $n \geq 3$ and $| V_{1} | \geq \dots \geq | V_{ℓ} |$ , and let $B_{i} = {V_{k} | e_{i (i + 1)} ≻_{t} V_{k} and | V_{k} | = i for some e_{i (i + 1)} \in E_{1}}$ and $b_{i} = | B_{i} |$ for $1 \leq i \leq ⌈ \frac{2 n}{3} ⌉$ . we continue our proof in the following cases.

$n = 3$ . Then $| V_{i} | \leq α = 2$ for each $i$ , and so $ℓ \geq 5$ , by Fact 2.5 (1). Now since the coloring function $({e_{12}, e_{03}}, {v_{1}, e_{23}}, {v_{0}, e_{13}}, {v_{2}, e_{01}}, {v_{3}, e_{02}})$ is a TD-coloring of $T (W_{3})$ , we have $χ_{d}^{t t} (W_{3}) = 5$ .
$n = 4$ . Then $| V_{i} | \leq α = 3$ for each $i$ , and so $ℓ \geq 5$ , Fact 2.5 (1). If $ℓ = 5$ , then $(| V_{1} |, | V_{2} |, \dots, | V_{5} |) = (3, 3, 3, 3, 1)$ which contradicts the Fact 2.5(2,4), or $(| V_{1} |, | V_{2} |, \dots, | V_{5} |) = (3, 3, 3, 2, 2)$ which contradicts the Fact 2.5 (2,3). So $ℓ \geq 6$ , and since $(V_{1}, \dots, V_{6})$ is a TD-coloring of $T (W_{4})$ where $V_{i} = {e_{0 i}, v_{i + 1}}$ for $1 \leq i \leq 3$ , $V_{4} = {e_{04}, v_{1}}$ , $V_{5} = {e_{12}, e_{34}} \cup {v_{0}}$ and $V_{6} = {e_{23}, e_{45}}$ , we have $χ_{d}^{t t} (W_{4}) = 6$ .
$n = 5$ . By the contrary, let $ℓ = 6$ . Then $2 b_{1} + b_{2} \geq 5$ (by Fact 2.5 (5)) and $(V_{1}, \dots, V_{6}) = (4, 4, 4, 2, 1, 1)$ (by Fact 2.5 (1)). But by considering the proof of Lemma 2.4, we know that all of the maximum independent sets in $T (W_{5})$ are the sets ${e_{0 i}, v_{i + 1}, e_{(i + 2) (i + 3)}, v_{i + 5}}$ for $1 \leq i \leq 5$ , which only two of them are disjoint. Thus $V_{i} \cap V_{j} \neq \emptyset$ for some $1 \leq i < j \leq 3$ , a contradiction. So $ℓ \geq 7$ , and since $(V_{1}, \dots, V_{7})$ is a TD-coloring of $T (W_{5})$ where $V_{1} = {v_{1}, v_{3}, e_{02}, e_{45}}$ , $V_{2} = {v_{2}, e_{34}, e_{05}}$ , $V_{3} = {e_{03}, v_{4}}$ , $V_{4} = {e_{01}, e_{23}}$ , $V_{5} = {e_{04}, v_{5}}$ , $V_{6} = {v_{0}, e_{15}}$ , $V_{7} = {e_{12}}$ , we have $χ_{d}^{t t} (W_{5}) = 7$ .
$n = 6$ . By the contrary, let $ℓ = 7$ . Then $6 \leq 2 b_{1} + b_{2} \leq 7$ by Fact 2.5 (5). Since obviousely $b_{1} \geq 4$ implies $| V_{1} | > α = 4$ , we assume $b_{1} \leq 3$ , and so $(b_{1}, b_{2}) = (3, 0)$ , $(3, 1)$ , $(3, 2)$ , $(3, 3)$ , $(3, 4)$ , $(2, 2)$ , $(2, 3)$ , $(2, 4)$ , $(2, 5)$ , $(1, 4)$ , $(1, 5)$ , $(1, 6)$ , $(0, 7)$ . Since $(b_{1}, b_{2}) = (3, 4)$ , $(2, 5)$ , $(1, 6)$ , $(0, 7)$ imply $\sum_{i = 1}^{7} | V_{i} | \neq 3 n + 1$ , and $(b_{1}, b_{2}) = (3, 1)$ , $(3, 2)$ , $(3, 3)$ , $(2, 2)$ , $(2, 3)$ , $(2, 4)$ , $(1, 4)$ , $(1, 5)$ imply $| V_{1} | > α = 4$ , which contradict Fact 2.5 (1), we may assume $(b_{1}, b_{2}) = (3, 0)$ . But this implies $(| V_{1} |, \dots, | V_{7} |) = (4, 4, 4, 4, 1, 1, 1)$ (by Fact 2.5 (1)) which is not possible. Because, by considering the proof of Lemma 2.4, the number of disjoint maximum independent sets in $T (W_{6})$ is at most three. So $ℓ \geq 8$ , and since the coloring function $(V_{1}, \dots, V_{8})$ is a TD-coloring of $T (W_{6})$ where $V_{1} = {e_{12}, e_{34}, e_{56}, v_{0}}$ , $V_{2} = {e_{23}, e_{45}, e_{16}}$ , $V_{3} = {e_{01}, v_{2}}$ , $V_{4} = {e_{02}, v_{3}}$ , $V_{5} = {e_{03}, v_{4}}$ , $V_{6} = {e_{04}, v_{5}}$ , $V_{7} = {e_{05}, v_{6}}$ , $V_{8} = {e_{06}, v_{1}}$ , we have $χ_{d}^{t t} (W_{6}) = 8$ .
$n = 7$ . By the contrary, let $ℓ = 8$ . Then $7 \leq 2 b_{1} + b_{2} \leq 8$ by Fact 2.5 (5). Since $| V_{1} | > α = 5$ when $b_{1} \geq 5$ , we have $b_{1} \leq 4$ , and so $(b_{1}, b_{2}) = (4, 0)$ , $(4, 1)$ , $(4, 2)$ , $(4, 3)$ , $(4, 4)$ , $(3, 1)$ , $(3, 2)$ , $(3, 3)$ , $(3, 4)$ , $(3, 5)$ , $(2, 3)$ , $(2, 4)$ , $(2, 5)$ , $(2, 6)$ , $(1, 5)$ , $(1, 6)$ , $(1, 7)$ , $(0, 8)$ . Since $(b_{1}, b_{2}) = (4, 4)$ , $(3, 5)$ , $(2, 6)$ , $(1, 7)$ , $(0, 8)$ imply $\sum_{i = 1}^{8} | V_{i} | \neq 3 n + 1$ and $(b_{1}, b_{2}) = (4, 1)$ , $(4, 2)$ , $(4, 3)$ , $(3, 3)$ , $(3, 4)$ , $(2, 4)$ , $(2, 5)$ , $(1, 5)$ , $(1, 6)$ imply $| V_{1} | > α = 5$ which contradict Fact 2.5 (1), we may assume $(b_{1}, b_{2}) = (4, 0)$ , $(3, 1)$ , $(3, 2)$ or $(2, 3)$ . But then we have $4 \leq | V_{3} | \leq | V_{2} | \leq | V_{1} | \leq 5$ , which is not possible. Because, by considering the proof of Lemma 2.4, the number of disjoint independent sets of cardinalities four or five in $T (W_{6})$ is at most two. So $ℓ \geq 9$ , and since the coloring function $(V_{1}, \dots, V_{9})$ is a TD-coloring of $T (W_{7})$ where $V_{1} = {e_{01}, e_{34}, e_{56}, v_{2}, v_{7}}$ , $V_{3} = {e_{12}, e_{45}, e_{67}, e_{03}}$ , $V_{5} = {e_{23}, e_{05}, v_{1}, v_{4}, v_{6}}$ , $V_{7} = {e_{17}, v_{3}, v_{5}}$ , $V_{2 i} = {e_{0 (2 i)}} (for 1 \leq i \leq 3)$ , $V_{8} = {v_{0}}$ , $V_{9} = {e_{07}}$ , we have $χ_{d}^{t t} (W_{7}) = 9$ .
$n \geq 8$ . Since the subgraph of $T (W_{n})$ induced by $E_{0} \cup {v_{0}}$ is isomorphic to a complete graph of order $n + 1$ , we have $χ_{d}^{t} (T (W_{n})) \geq n + 1$ . Since the sets $S_{e} = {e_{0 (2 i)} | 1 \leq i \leq ⌊ \frac{n}{2} ⌋} \cup {v_{0}}$ for even $n$ , and $S_{o} = {e_{0 (2 i)} | 1 \leq i \leq ⌊ \frac{n}{2} ⌋} \cup {v_{0}, e_{0 n}}$ for odd $n$ , are two min-TD-sets of $T (W_{n})$ of cardinality $⌈ \frac{n}{2} ⌉ + 1$ by Proposition 2.2, we have $χ_{d}^{t t} (W_{n}) \leq ⌈ \frac{n}{2} ⌉ + 1 + χ (G [V (T (W_{n})) - S]),$ by Proposition 2.1 in which $S = S_{e}$ for even $n$ and $S = S_{o}$ for odd $n$ . So it is sufficient to prove $χ (G [V (T (W_{n})) - S]) = ⌊ \frac{n}{2} ⌋$ . Since the subgraph induced by ${e_{0 (2 i - 1)} | 1 \leq i \leq ⌊ \frac{n}{2} ⌋}$ is a complete graph, we have $χ (G [V (T (W_{n})) - S]) \geq ⌊ \frac{n}{2} ⌋$ . On the other hand, since, for even $n$ the coloring function $f_{e}$ with the criterion $f_{e} (w) \equiv {\begin{cases} i (\mod ⌊ \frac{n}{2} ⌋) & if w = e_{0 (2 i + 1)}, \\ i + 1 (\mod ⌊ \frac{n}{2} ⌋) & if w = e_{(2 i + 1) (2 i + 2)} or v_{2 i + 3}, \\ i + 2 (\mod ⌊ \frac{n}{2} ⌋) & if w = v_{2 i + 2}, \\ i + 3 (\mod ⌊ \frac{n}{2} ⌋) & if w = e_{(2 i + 2) (2 i + 3)}, \end{cases}$ when $0 \leq i \leq ⌊ \frac{n}{2} ⌋ - 1$ is a proper coloring of $G [V (T (W_{n})) - S_{e}$ , and for odd $n$ the coloring function $f_{o}$ with the criterion $f_{o} (w) \equiv {\begin{cases} i (\mod ⌊ \frac{n}{2} ⌋) & if w = e_{0 (2 i + 1)}, \\ i + 1 (\mod ⌊ \frac{n}{2} ⌋) & if w = e_{(2 i + 1) (2 i + 2)} or v_{2 i + 3}, \\ i + 2 (\mod ⌊ \frac{n}{2} ⌋) & if w = v_{2 i + 2}, \\ i + 3 (\mod ⌊ \frac{n}{2} ⌋) & if w = e_{(2 i + 2) (2 i + 3)}, \\ 2 & if w = e_{(n - 1) n}, \\ 3 & if w = v_{n}, \end{cases}$ when $0 \leq i \leq ⌊ \frac{n}{2} ⌋ - 1$ is a proper coloring of $G [V (T (W_{n})) - S_{o}$ , we have $χ (G [V (T (W_{n})) - S]) = ⌊ \frac{n}{2} ⌋$ .

Proposition 2.6 shows that the upper bound given in Proposition 2.1 is tight for wheels of order more than 8. Figure 2 shows a min-TDT-coloring of $W_{5}$ (left) and its corresponding min-TD-coloring of $T (W_{5})$ (right) as an example.

Figure 2 A min-TDT-coloring $(V_{1}, \dots, V_{7})$ of $W_{5}$ (left) and its corresponding min-TD-coloring of $T (W_{5})$ (right) where $V_{1} = {v_{1}, v_{3}, e_{02}, e_{45}}$ , $V_{2} = {v_{2}, e_{34}, e_{05}}$ , $V_{3} = {v_{0}, e_{15}}$ , $V_{4} = {v_{4}, e_{03}}$ , $V_{5} = {v_{5}, e_{04}}$ , $V_{6} = {e_{01}, e_{23}}$ and $V_{3} = {e_{12}})$

3. Complete bipartite graphs

Here, we calculate the total dominator total chromatic number of a complete bipartite graph $K_{m, n} = (V \cup U, E)$ in which $V \cup U$ is the partition of its vertex set to the independent sets $V = {v_{i} : 1 \leq i \leq m}$ , $U = {u_{j} : 1 \leq j \leq n}$ and $E = {e_{i j} | 1 \leq i \leq m, 1 \leq j \leq n}$ is its edge set.

Proposition 3.1. For any complete bipartite graph $K_{m, n}$ in which $n \geq m \geq 1$ , $χ_{d}^{t t} (K_{m, n}) = {\begin{cases} m + n & if m = 1, 2 and (m, n) \neq (1, 1), \\ m + n + 1 & if m \geq 3 or (m, n) = (1, 1) . \end{cases}$

Proof. Let $K_{m, n}$ be the complete bipartite graph $(V \cup U, E)$ of order $n + m \geq 2$ . Hence $V \cup U \cup E$ is a partition of the vertex set $T (K_{m, n})$ where $E = {e_{i j} | 1 \leq i \leq m, 1 \leq j \leq n}$ . Since $T (K_{1, 1}) ≅ K_{3}$ implies $χ_{d}^{t t} (K_{1, 1}) = 3$ , we assume $n > m = 1$ . Let $f = (V_{1}, V_{2}, \dots, V_{ℓ})$ be a minimal TD-coloring of $T (K_{m, n})$ . Since the subgraph of $T (K_{m, n})$ induced by ${v_{1}, e_{11}, \dots, e_{1 n}}$ is a complete graph of order $n + 1$ , we have $χ_{d}^{t} (T (K_{m, n}) \geq n + 1$ . Since $(V_{1}, V_{2}, \dots, V_{n + 1})$ is a TD-coloring of $T (K_{1, n})$ where $V_{1} = {e_{11}, u_{n}}$ , $V_{i} = {e_{1 i}, u_{i - 1}}$ for $2 \leq i \leq n$ , $V_{n + 1} = {v_{1}}$ , which implies $χ_{d}^{t t} (K_{1, n}) = n + 1$ , we continue our proof in the following two cases.

Case 1. $n \geq m = 2$ . Let $χ_{d}^{t t} (K_{m, n}) = n + 1$ , and let $E_{i} = {e_{i j} | 1 \leq j \leq n}$ for $i = 1, 2$ . Since $T (K_{m, n}) [E_{1}] ≅ T (K_{m, n}) [E_{2}] ≅ K_{n}$ we have to color the vertices in $E_{1}$ (and also in $E_{2}$ ) by $n$ different colors. On the other hand, since $T (K_{m, n}) [E_{1} \cup E_{2}] ≅ K_{n} K_{2}$ we conclude that $e_{1 j}$ and $e_{2 j}$ are not in a same color class when $1 \leq j \leq n$ . Without loss of generality, we may assume $e_{1 j} \in V_{j}$ for $1 \leq j \leq n$ and $v_{1} \in V_{n + 1}$ . If $f (E_{2}) = {1, 2, \dots, n}$ , then $v_{1} ⊁_{t} V_{k}$ for each $1 \leq k \leq n$ , because $N_{T (K_{m, n})} (v_{1}) \cap E_{2} = \emptyset$ and $| V_{k} | \geq 2$ for each $1 \leq k \leq n$ . So $n + 1 \in f (E_{2})$ , and a color, say $1$ , is not in $f (E_{2})$ . This implies $f (v_{2}) = 1$ and so $v_{1} ⊁_{t} V_{k}$ for each $1 \leq k \leq n + 1$ . So $ℓ \geq n + 2 = n + m$ , and since, by assumptions $V_{1} = {e_{11}, e_{2 n}}$ , $V_{i} = {e_{1 i}, e_{2 (i - 1)}}$ for $2 \leq i \leq n$ , $V_{n + 1} = V$ and $V_{n + 2} = U$ , the coloring function $(V_{1}, V_{2}, \dots, V_{n + 2})$ is a TD-coloring of $T (K_{m, n})$ , we have $χ_{d}^{t t} (K_{m, n}) = n + 2$ .

Case 2. $n \geq m \geq 3$ . For $1 \leq i \leq m$ let $E_{i} = {e_{i j} | 1 \leq j \leq n}$ , and for $1 \leq j \leq n$ let $E_{j}^{'} = {e_{i j} | 1 \leq i \leq m}$ . It can be easily verified that $T (K_{m, n}) [E_{i}] ≅ K_{n}$ , $T (K_{m, n}) [E_{j}^{'}] ≅ K_{m}$ , $T (K_{m, n}) [E_{1} \cup E_{2} \cup \dots \cup E_{m}] ≅ T (K_{m, n}) [E_{1}^{'} \cup E_{2}^{'} \cup \dots \cup E_{n}^{'}] ≅ K_{n} K_{m}$ and $T (K_{m, n}) [E_{i} \cup {v_{i}}] ≅ K_{n + 1}$ , $T (K_{m, n}) [E_{j}^{'} \cup {u_{j}}] ≅ K_{m + 1}$ . By proving $ℓ \geq n + m + 1$ in the following two subcases, and by considering this fact that the coloring function $g$ with the criterion $\begin{array}{ll} g (e_{i j}) \equiv j - i + 1 (\mod n) & if 1 \leq i \leq m and 1 \leq j \leq n, \\ g (v_{i}) = n + i & if 1 \leq i \leq m, and \\ g (u_{i}) = n + m + 1 & if 1 \leq i \leq n, \end{array}$ is a TD-coloring of $T (K_{m, n})$ with $m + n + 1$ color classes, we have $χ_{d}^{t t} (K_{m, n}) = m + n + 1$ .

2.1. $f (E_{1} \cup E_{2} \cup \dots \cup E_{m}) = {1, 2, \dots, n}$ . Since for each $1 \leq i \leq m$ , $v_{i} ≻_{t} V_{k_{i}}$ implies $f (V_{k_{i}}) \cap {1, 2, \dots, n} = \emptyset$ (because every color $1 \leq i \leq n$ appears $m \geq 2$ times) and $V_{k_{i}} \subseteq U$ , we have $ℓ \geq n + 1$ . On the other hand, we see that for each $1 \leq i \leq m$ and $1 \leq j \leq n$ , $e_{i j} ≻_{t} V_{k_{i j}}$ implies $V_{k_{i j}} \subset {v_{i}, u_{j}}$ . Then, by the minimality of $f$ , $n \geq m$ implies $V_{k_{i j}} = {v_{i}}$ for each $1 \leq i \leq m$ . Now since $f (V) \cap f (U) = \emptyset$ , we have $ℓ \geq n + m + 1$ .
2.2. ${1, 2, \dots, n + 1} \subseteq f (E_{1} \cup E_{2} \cup \dots \cup E_{m})$ . We assume the minimal TD-coloring $f$ of $T (K_{m, n})$ is best in this meaning that for every minimal TD-coloring $g$ of $T (K_{m, n})$ , $| f (E_{1} \cup E_{2} \cup \dots \cup E_{m}) | \leq | g (E_{1} \cup E_{2} \cup \dots \cup E_{m}) |$ . Then for each $1 \leq i \leq m$ , $v_{i} ≻_{t} V_{k_{i}}$ implies $V_{k_{i}} \subseteq U \cup E_{i}$ and specially if also $e_{i j} \in V_{k_{i}}$ for some $1 \leq i \leq n$ , then $u_{j} \notin V_{k_{i}}$ and $f (e_{i j}) \notin f (E_{1} \cup E_{2} \cup \dots \cup E_{m}) - f (E_{i})$ , that is, the color of $e_{i j}$ does not appear in the other vertices in $E_{1} \cup E_{2} \cup \dots \cup E_{m} - E_{i}$ . If every color in $f (E_{1} \cup E_{2} \cup \dots \cup E_{m})$ is appear at least two times, then similar to Case 1, we can prove that at least $m + 1$ new color are needed for coloring of $V \cup U$ , which implies $ℓ \geq n + m + 1$ . Therefore, we assume there exists at least one color which is used for coloring of only one vertex in $E_{1} \cup E_{2} \cup \dots \cup E_{m}$ . For $1 \leq i \leq m$ let $r_{i}$ be the number of colors which are used only for coloring of one vertex from $E_{i} - (E_{1} \cup \dots \cup E_{i - 1})$ . Without loss of generality, we may assume $r_{1} \geq r_{2} \geq \dots \geq r_{m}$ . We know $| f (E_{i}) | = n$ for each $i$ . Since $| f (E_{2}) \cap f (E_{1}) | \leq n - r_{1}$ , we have $| f (E_{2}) - f (E_{1}) | \geq r_{1}$ . In a similar way, we have $| f (E_{k}) - \cup_{i = 1}^{k - 1} f (E_{i}) | \geq \sum_{i = 1}^{k - 1} r_{i}$ for $3 \leq k \leq m$ . By summing this inequalities, we obtain $\begin{matrix} (2) & | f (E_{1} \cup E_{2} \cup \dots \cup E_{m}) | \geq n + (m - 1) r_{1} + (m - 2) r_{2} + \dots + r_{m - 1} . \end{matrix}$

Since (2) implies $ℓ \geq n + m + 1$ when $r_{1} \geq 2$ , we may assume $r_{1} = 1$ . If $r_{1} = r_{2} = r_{3} = 1$ , then $m \geq 4$ and again (2) implies $ℓ \geq n + m + 1$ . Otherwise, there exists at least a vertex $e_{i j} \in E_{i}$ for some $3 \leq i \leq m$ such that if $e_{i j} ≻_{t} V_{k_{i j}}$ , then $V_{k_{i j}} \cap f (E_{1} \cup E_{2} \cup \dots \cup E_{m}) = \emptyset$ , that is, at least a new color is needed, and $V_{k_{i j}} \subset {v_{i}, u_{j}}$ . Since $f (V) \cap f (U) = \emptyset$ , $V_{k_{i j}} = {v_{i}}$ implies at least one new color is used to color some vertex in $U$ , and similarly $V_{k_{i j}} = {u_{j}}$ implies that at least one new color is used to color some vertex in $V$ . Therefore (2) implies $ℓ \geq (n + m - 1) + 1 + 1 \geq n + m + 1$ .

Since $χ_{d}^{t t} (G) = n$ when $G$ is a wheel of order $n \geq 9$ (by Proposition 2.6) or $G$ is $K_{1, q}$ or $K_{2, q}$ of order $n \geq 3$ (by Proposition 3.1), we have the following theorem.

Theorem 3.2. For any

n \geq 3

, there exists a graph

G

of order

n

with

χ_{d}^{t t} (G) = n

4. Complete graphs

From [9], we know that for any complete graph $K_{n}$ of order $n \geq 2$ , $\begin{matrix} (3) & χ_{d}^{t t} (K_{n}) \leq ⌈ \frac{5 n}{3} ⌉ . \end{matrix}$ Here, we show that the upper bound in (3) is tight when $11 \neq n \geq 9$ . Here, we assume the vertex set of the complete graph $K_{n}$ is the set $V = {v_{i} | 1 \leq i \leq n}$ , and the vertex set of the total of it is $V (T (K_{n})) = V \cup E$ where $E = {e_{i j} | 1 \leq i < j \leq n}$ . First we clarify more details on the total of a complete graph in the next observation. To more underestanding the observation, $T (K_{5})$ is shown in Figure 3 as an example.

Figure 3 $T (K_{5})$ and its six edge-disjoint copies of $K_{5}$

Observation 4.1. Let $T (K_{n})$ be the total of a complete graph $K_{n}$ of order $n \geq 2$ with the vertex set $V = {v_{i} | 1 \leq i \leq n}$ . Then the following states are hold.

$T (K_{n})$ is $2 (n - 1)$ -regular and $T (K_{n}) = K_{n}^{v_{0}} \cup K_{n}^{v_{1}} \cup \dots \cup K_{n}^{v_{n}}$ is the partition of $T (K_{n})$ to $n + 1$ edge-disjoint copies of $K_{n}$ where $K_{n}^{v_{0}} = K_{n}$ and $V (K_{n}^{v_{i}}) = {v_{i}} \cup {e_{i j} | 1 \leq j \neq i \leq n}$ for $1 \leq i \leq n$ .
$L (K_{n}) = T (K_{n}) - K_{n} = (K_{n}^{v_{1}} - {v_{1}}) \cup \dots \cup (K_{n}^{v_{n}} - {v_{n}})$ is the partition of the line graph of $K_{n}$ to $n$ edge-disjoint copies of $K_{n - 1}$ .
$V (K_{n}^{v_{i}}) \cap V (K_{n}^{v_{j}}) = {e_{i j}}$ for each $1 \leq i < j \leq n$ .
$V (K_{n}^{v_{i}}) \cap V (K_{n}^{v_{0}}) = {v_{i}}$ for each $1 \leq i \leq n$ .
For every $x \in V (T (K_{n}))$ , $N (x) = V (K_{n}^{v_{i}}) \cup V (K_{n}^{v_{j}}) - {x}$ for some $0 \leq i < j \leq n$ .
For each $1 \leq i \leq n$ , the function $ϕ_{i}$ on $V (T (K_{n}))$ with the criterion $ϕ_{i} (x) = {\begin{cases} v_{i} & if x = v_{i}, \\ v_{j} & if x = e_{i j}, \\ e_{i j} & if x = v_{j}, \\ x & otherwise, \end{cases}$ is an authomorsim of $T (K_{n})$ which replaces $K_{n}$ with $K_{n}^{v_{i}}$ . And so $ϕ_{j} \circ ϕ_{i}^{- 1}$ is an authomorsim of $T (K_{n})$ which replaces $K_{n}^{v_{i}}$ with $K_{n}^{v_{j}}$ .

We recall a needed proposition from [8].

Proposition 4.2. [8] For any complete graph

K_{n}

of order

n \geq 2

$γ_{t m} (K_{n}) = γ_{t} (T (K_{n})) = ⌈ \frac{5 n}{3} ⌉ - n$ ,
$α_{m i x} (K_{n}) = α (T (K_{n})) = ⌈ \frac{n}{2} ⌉$ .

Some facts on a minimal TD-coloring of $T (K_{n})$ are listed here.

Fact 4.3. Let $f = (V_{1}, V_{2}, \dots, V_{ℓ})$ be a minimal TD-coloring of $T (K_{n})$ in which $| V_{1} | \geq | V_{2} | \geq \dots \geq | V_{ℓ} |$ , and let $A_{i} = {V_{k} | v ≻_{t} V_{k} and | V_{k} | = i for some v \in V \cup E}$ be a set of cardinality $a_{i}$ for $1 \leq i \leq α = ⌈ \frac{n}{2} ⌉$ . Then the following facts are hold.

$\sum_{i = 1}^{ℓ} | V_{i} | = \frac{n (n + 1)}{2}$ and $\sum_{i = 1}^{ℓ} | C N (V_{i}) | \geq \frac{n (n + 1)}{2}$ by $| V | = \sum_{i = 1}^{ℓ} | V_{i} |$ and $(C N (V_{i}) = V)$ , respectively. Also $| V_{k} | \leq ⌈ \frac{n}{2} ⌉$ for each $1 \leq k \leq ℓ$ .
For any $v \in V \cup E$ , if $v ≻_{t} V_{k}$ for some $1 \leq k \leq ℓ$ , then $| V_{k} | \leq 2$ . Because $N (v) = V (K_{n}^{v_{i}}) \cup V (K_{n}^{v_{j}}) - {v}$ , for some $0 \leq i < j \leq n$ $(b y$ $O b s e r v a t i o n$ 4.1 $(5))$ , implies $| V_{k} \cap V (K_{n}^{v_{i}}) | \leq 1$ and $| V_{k} \cap V (K_{n}^{v_{j}}) | \leq 1$ .
If $V_{k} = {v_{i}, e_{p q}}$ for different indices $i$ , $p$ , $q$ , then $C N (V_{k}) = {v_{p}, v_{q}, e_{i p}, e_{i q}}$ , and if $V_{k} = {e_{r s}, e_{p q}}$ for different indices $p$ , $q$ , $r$ , $s$ , then $C N (V_{k}) = {e_{r p}, e_{r q}, e_{s p}, e_{s q}}$ .
If $V_{k} = {v_{i}}$ for some $i$ , then $C N (V_{k}) = V \cup {e_{i j} | 1 \leq j \neq i \leq n} - {v_{i}}$ , and if $V_{k} = {e_{p q}}$ for some $p \neq q$ , then $C N (V_{k}) = {e_{i j} | | {p, q} \cap {i, j} | = 1} \cup {v_{p}, v_{q}}$ .
$(2 n - 2) a_{1} + 4 a_{2} \geq \frac{n (n + 1)}{2}$ . Because $\begin{array}{llll} \frac{n (n + 1)}{2} & = & | V \cup E | \\ \leq & Σ_{| V_{k} | \leq 2} | C N (V_{k}) | & (by (2)) \\ = & Σ_{| V_{k} | = 1} | C N (V_{k}) | + Σ_{| V_{k} | = 2} | C N (V_{k}) | \\ \leq & (2 n - 2) a_{1} + 4 a_{2} . \end{array}$
$⌈ \frac{5 n}{3} ⌉ - n \leq a_{1} + a_{2} \leq ℓ$ . Because the set $S$ with this property that $| S \cap V_{i} | = 1$ for each $V_{i} \in A_{1} \cup A_{2}$ is a TD-set of $T (K_{n})$ $($ by $(2)$ and Proposition 4.2 $(2)$ for left $)$ , and $a_{1} + \dots + a_{α} = ℓ$ $($ for right $)$ .
$⌈ \frac{n (n + 1) / 2 - 4 (⌈ 5 n / 3 ⌉ - n)}{2 n - 6} ⌉ \leq a_{1} \leq ⌊ \frac{α ℓ - n (n + 1) / 2}{α - 1} ⌋$ . Because the lower bound can be obtained by $(5, 6)$ , and the upper bound can be obtained by $\begin{array}{llll} \frac{n (n + 1)}{2} - a_{1} & = & | V (T (K_{n})) | - | A_{1} | \\ = & Σ_{| V_{i} | \geq 2} | V_{i} | \\ \leq & (ℓ - a_{1}) α . \end{array}$
$⌈ \frac{(2 n - 2) (⌈ 5 n / 3 ⌉ - n) - n (n + 1) / 2}{2 n - 6} ⌉ \leq a_{2} \leq ℓ - a_{1}$ $($ by $(5, 6, 7))$ .
For any $V_{i} = {e_{r s}}, V_{j} = {e_{p q}} \in A_{1}$ , $| C N (V_{i}) \cap C N (V_{j}) | = {\begin{cases} 4 & if {r, s} \cap {p, q} = \emptyset, \\ n - 1 & if {r, s} \cap {p, q} \neq \emptyset . \end{cases}$ Notice $e_{i i}$ is the same $v_{i}$ .

Theorem 4.4. For any complete graph $K_{n}$ of order $n \geq 2$ , $χ_{d}^{t t} (K_{n}) = {\begin{cases} ⌈ \frac{5 n}{3} ⌉ - 2 & if n = 3, 4, 5, \\ ⌈ \frac{5 n}{3} ⌉ - 1 & if n = 2, 6, 7, 8, 11 \\ ⌈ \frac{5 n}{3} ⌉ & if n \geq 9 and n \neq 11. \end{cases}$

Proof. Since the result holds for $2 \leq n \leq 4$ by Proposition 2.6 and some results in [8], we may assume $n \geq 5$ . We recall from Proposition 4.2 that $α_{m i x} (K_{n}) = α (T (K_{n})) = ⌈ \frac{n}{2} ⌉$ . Let $f = (V_{1}, V_{2}, \dots, V_{ℓ})$ be a minimal TD-coloring of $T (K_{n})$ in which $| V_{1} | \geq | V_{2} | \geq \dots \geq | V_{ℓ} |$ , and let $A_{i} = {V_{k} | v ≻_{t} V_{k} and | V_{k} | = i for some v \in V \cup E}$ be a set of cardinality $a_{i}$ for $1 \leq i \leq ⌈ \frac{n}{2} ⌉$ . We continue our proof in the following cases.

Case 1. $5 \leq n \leq 8$ or $n = 11$ .

$n = 5$ . Let $ℓ = 6$ . Then $(a_{1}, a_{2}) = (0, 5)$ , $(0, 6)$ , $(1, 5)$ . Because $0 \leq a_{1} \leq 1$ and $5 \leq a_{2} \leq 6$ by Fact 4.3 (7,8). Since $(a_{1}, a_{2}) = (0, 6)$ , $(1, 5)$ imply $\sum_{i = 1}^{6} | V_{i} | \neq \frac{n (n + 1)}{2}$ , and $(a_{1}, a_{2}) = (0, 5)$ implies $| V_{1} | > ⌈ \frac{n}{2} ⌉ = 3$ , which contradict Fact 4.3 (1), we have $ℓ \geq 7$ . Now since $(V_{1}, \dots, V_{7})$ is a TD-coloring of $T (K_{5})$ where $V_{1} = {v_{3}, e_{12}, e_{45}}$ , $V_{2} = {v_{4}, e_{23}, e_{15}}$ , $V_{3} = {v_{5}, e_{13}, e_{24}}$ , $V_{4} = {e_{25}, e_{34}}$ , $V_{5} = {e_{35}, e_{14}}$ , $V_{6} = {v_{1}}$ , $V_{7} = {v_{2}}$ , we have $χ_{d}^{t t} (K_{5}) = 7 = ⌈ \frac{5 n}{3} ⌉ - 2$ .
$n = 6$ . Let $ℓ = 8$ . Then $(a_{1}, a_{2}) = (1, 4)$ , $(1, 5)$ , $(1, 6)$ , $(1, 7)$ . Because $a_{1} = 1$ and $4 \leq a_{2} \leq 7$ by Fact 4.3 (7,8). Since $(a_{1}, a_{2}) = (1, 7)$ implies $\sum_{i = 1}^{8} | V_{i} | \neq \frac{n (n + 1)}{2}$ , and $(a_{1}, a_{2}) = (1, 4)$ , $(1, 5)$ , $(1, 6)$ imply $| V_{1} | > ⌈ \frac{n}{2} ⌉ = 3$ , which contradict Fact 4.3 (1), we have $ℓ \geq 9$ . Now since $(V_{1}, \dots, V_{9})$ is a TD-coloring of $T (K_{6})$ where $V_{1} = {v_{3}, e_{12}, e_{45}}$ , $V_{2} = {v_{4}, e_{13}, e_{26}}$ , $V_{3} = {v_{5}, e_{16}, e_{23}}$ , $V_{4} = {v_{6}, e_{14}, e_{25}}$ , $V_{5} = {e_{36}, e_{15}, e_{24}}$ , $V_{6} = {e_{34}, e_{56}}$ , $V_{7} = {e_{35}, e_{46}}$ , $V_{8} = {v_{1}}$ , $V_{9} = {v_{2}}$ , we have $χ_{d}^{t t} (K_{6}) = 9 = ⌈ \frac{5 n}{3} ⌉ - 1$ .
$n = 7$ . Let $ℓ = 10$ . Then $(a_{1}, a_{2}) = (1, 4)$ , $(1, 5)$ , $(1, 6)$ , $(1, 7)$ , $(1, 8)$ , $(1, 9)$ , $(2, 4)$ , $(2, 5)$ , $(2, 6)$ , $(2, 7)$ , $(2, 8)$ , $(3, 4)$ , $(3, 5)$ , $(3, 6)$ , $(3, 7)$ , $(4, 4)$ , $(4, 5)$ , $(4, 6)$ . Because $1 \leq a_{1} \leq 4$ and $4 \leq a_{2} \leq 10 - a_{1}$ by Fact 4.3 (7,8). Since $(a_{1}, a_{2}) = (1, 9)$ , $(2, 8)$ , $(3, 7)$ , $(4, 6)$ imply $\sum_{i = 1}^{10} | V_{i} | \neq \frac{n (n + 1)}{2}$ , and $(a_{1}, a_{2}) = (1, 5)$ , $(1, 6)$ , $(1, 7)$ , $(1, 8)$ , $(2, 4)$ , $(2, 5)$ , $(2, 6)$ , $(2, 7)$ , $(3, 4)$ , $(3, 5)$ , $(3, 6)$ , $(4, 4)$ , $(4, 5)$ imply $| V_{1} | > ⌈ \frac{n}{2} ⌉ = 4$ , which contradict Fact 4.3 (1), we have $(a_{1}, a_{2}) = (1, 4)$ . By Observation 4.1(6), we may assume $V_{10} = {v_{i}}$ for some $1 \leq i \leq n$ . Then $v_{i} ≻_{t} V_{k}$ for some $k \neq 10$ implies $V_{k} = {v_{p}, e_{i q}}$ for some three different indices $i$ , $p$ , $q$ . Since $\begin{array}{llll} | C N (V_{k}) \cup C N (V_{10}) | & = & | C N (V_{k}) | + | C N (V_{10}) | - | C N (V_{k}) \cap C N (V_{10}) | \\ = & 4 + 12 - 4 \\ = & 12 \end{array}$ by Fact 4.3 (3,4), we reach to the contradiction $\begin{array}{llll} 28 & = & \frac{n (n + 1)}{2} \\ \leq & Σ_{i = 6}^{10} | C N (V_{k}) | \\ \leq & Σ_{k \neq i = 6}^{9} | C N (V_{k}) | + Σ_{i = k, 10} | C N (V_{i}) | \\ \leq & 3 \times 4 + 12 & (by Fact 4.3 (3)) \\ = & 24. \end{array}$ Thus $ℓ \geq 11$ , and since $(V_{1}, \dots, V_{11})$ is a TD-coloring of $T (K_{7})$ where $V_{1} = {v_{4}, e_{16}, e_{25}, e_{37}}$ , $V_{2} = {v_{5}, e_{67}, e_{13}, e_{24}}$ , $V_{3} = {v_{6}, e_{15}, e_{23}, e_{47}}$ , $V_{4} = {v_{7}, e_{35}, e_{26}, e_{14}}$ , $V_{5} = {v_{3}, e_{46}, e_{57}}$ , $V_{6} = {v_{1}, e_{27}, e_{36}}$ , $V_{7} = {v_{2}, e_{34}}$ , $V_{8} = {e_{12}}, V_{9} = {e_{45}}$ , $V_{10} = {e_{56}}, V_{11} = {e_{17}}$ , we have $χ_{d}^{t t} (K_{7}) = 11 = ⌈ \frac{5 n}{3} ⌉ - 1$ .
$n = 8$ . Let $ℓ = 12$ . Then $(a_{1}, a_{2}) = (2, 5)$ , $(2, 6)$ , $(2, 7)$ , $(2, 8)$ , $(2, 9)$ , $(2, 10)$ , $(3, 5)$ , $(3, 6)$ , $(3, 7)$ , $(3, 8)$ , $(3, 9)$ , $(4, 5)$ , $(4, 6)$ , $(4, 7)$ , $(4, 8)$ . Because $2 \leq a_{1} \leq 4$ and $5 \leq a_{2} \leq 12 - a_{1}$ by Fact 4.3 (7,8). Since $(a_{1}, a_{2}) = (2, 10)$ , $(3, 9)$ , $(4, 8)$ imply $\sum_{i = 1}^{12} | V_{i} | \neq \frac{n (n + 1)}{2}$ , and $(a_{1}, a_{2}) = (2, 5)$ , $(2, 6)$ , $(2, 7)$ , $(2, 8)$ , $(2, 9)$ , $(3, 5)$ , $(3, 6)$ , $(3, 7)$ , $(3, 8)$ , $(4, 5)$ , $(4, 6)$ , $(4, 7)$ imply $| V_{1} | > ⌈ \frac{n}{2} ⌉ = 4$ , which contradict Fact 4.3 (1), we have $ℓ \geq 13$ . Now since $(V_{1}, \dots, V_{13})$ is a TD-coloring of $T (K_{8})$ where $V_{1} = {v_{8}, e_{13}, e_{24}, e_{56}}$ , $V_{2} = {v_{7}, e_{25}, e_{36}, e_{48}}$ , $V_{3} = {v_{6}, e_{18}, e_{27}, e_{34}}$ , $V_{4} = {v_{5}, e_{16}, e_{28}, e_{37}}$ , $V_{5} = {v_{4}, e_{17}, e_{26}, e_{35}}$ , $V_{6} = {v_{2}, e_{15}, e_{47}, e_{38}}$ , $V_{7} = {e_{57}, e_{68}}$ , $V_{8} = {e_{46}, e_{58}}$ , $V_{9} = {e_{45}, e_{67}}$ , $V_{10} = {e_{14}, e_{78}}$ , $V_{11} = {v_{3}, e_{12}}$ , $V_{12} = {e_{23}}$ , $V_{13} = {v_{1}}$ , we have $χ_{d}^{t t} (K_{8}) = 13 = ⌈ \frac{5 n}{3} ⌉ - 1$ .
$n = 11$ . Let $ℓ = ⌈ \frac{5 n}{3} ⌉ - 2 = 17$ . Then $(a_{1}, a_{2}) = (3, 6)$ , $(3, 7)$ , $(3, 8)$ , $(3, 9)$ , $(3, 10)$ , $(3, 11)$ , $(3, 12)$ , $(3, 13)$ , $(3, 14)$ , $(4, 6)$ , $(4, 7)$ , $(4, 8)$ , $(4, 9)$ , $(4, 10)$ , $(4, 11)$ , $(4, 12)$ , $(4, 13)$ , $(5, 6)$ , $(5, 7)$ , $(5, 8)$ , $(5, 9)$ , $(5, 10)$ , $(5, 11)$ , $(5, 12)$ , $(6, 6)$ , $(6, 7)$ , $(6, 8)$ , $(6, 9)$ , $(6, 10)$ , $(6, 11)$ , $(7, 6)$ , $(7, 7)$ , $(7, 8)$ , $(7, 9)$ , $(7, 10)$ . Because $3 \leq a_{1} \leq 7$ and $6 \leq a_{2} \leq 17 - a_{1}$ by Fact 4.3 (7,8). Since $\sum_{i = 1}^{17} | V_{i} | \neq \frac{n (n + 1)}{2}$ when $(a_{1}, a_{2}) = (3, 14)$ , $(4, 13)$ , $(5, 12)$ , $(6, 11)$ , $(7, 10)$ and $| V_{1} | > ⌈ \frac{n}{2} ⌉ = 6$ in the other cases, which contradict Fact 4.3 (1), we have $ℓ \geq 18$ . Now since $(V_{1}, \dots, V_{18})$ is a TD-coloring of $T (K_{11})$ where $V_{1} = {v_{11}, e_{1 (10)}, e_{26}, e_{37}, e_{48}, e_{59}}$ , $V_{2} = {v_{10}, e_{19}, e_{28}, e_{35}, e_{46}, e_{7 (11)}}$ , $V_{3} = {v_{9}, e_{1 (11)}, e_{27}, e_{34}, e_{8 (10)}, e_{56}}$ , $V_{4} = {v_{8}, e_{14}, e_{2 (11)}, e_{39}, e_{6 (10)}, e_{57}}, V_{5} = {v_{7}, e_{18}, e_{29}, e_{36}, e_{4 (10)}, e_{5 (11)}}, V_{6} = {v_{4}, e_{15}, e_{2 (10)}, e_{3 (11)}, e_{68}, e_{79}}$ , $V_{7} = {v_{5}, e_{16}, e_{24}, e_{3 (10)}, e_{9 (11)}}$ , $V_{8} = {v_{6}, e_{17}, e_{25}, e_{38}, e_{49}}$ , $V_{9} = {v_{3}, e_{12}, e_{4 (11)}, e_{58}, e_{7 (10)}}$ , $V_{10} = {e_{6 (11)}, e_{9 (10)}}$ , $V_{11} = {e_{47}, e_{5 (10)}}$ , $V_{12} = {e_{89}, e_{(10) (11)}}$ , $V_{13} = {v_{2}, e_{13}}$ , $V_{14} = {e_{67}, e_{8 (11)}}$ , $V_{15} = {e_{69}, e_{78}}$ , $V_{16} = {v_{1}}$ , $V_{17} = {e_{23}}$ , $V_{18} = {e_{45}}$ , we have $χ_{d}^{t t} (K_{11}) = 18 = ⌈ \frac{5 n}{3} ⌉ - 1$ .

Case 2. $n \geq 9$ and $n \neq 11$ . Let $ℓ = ⌈ \frac{5 n}{3} ⌉ - 1$ , and let $\begin{array}{ll} m_{1} = ⌈ \frac{n (n + 1) / 2 - 4 (⌈ 5 n / 3 ⌉ - n)}{2 n - 6} ⌉, & M_{1} = ⌊ \frac{α ℓ - n (n + 1) / 2}{α - 1} ⌋, \\ m_{2} = ⌈ \frac{(2 n - 2) (⌈ 5 n / 3 ⌉ - n) - n (n + 1) / 2}{2 n - 6} ⌉, & M_{2} = ℓ - a_{1} . \end{array}$

Then $(a_{1}, a_{2}) = (x_{1} + i, x_{2} + j)$ for some $0 \leq i \leq M_{1} - m_{1}$ and some $0 \leq j \leq M_{2} - m_{2}$ . In the following subcases, we show that $ℓ = ⌈ \frac{5 n}{3} ⌉ - 1$ leads us to a contrdiction.

Either $n$ is even or $n$ is odd and $(a_{1}, a_{2}) \neq (m_{1}, m_{2})$ . Then, by Fact 4.3 (1), we must have $a_{1} + a_{2} \leq ℓ - 1$ and $| V_{1} | \leq ⌈ \frac{n}{2} ⌉$ , and so by assumptions $a_{1} = m_{1} + i$ and $a_{2} = m_{2} + j$ for some $0 \leq i \leq M_{1} - m_{1}$ and some $0 \leq j \leq M_{2} - m_{2}$ , we have $\begin{array}{llll} \sum_{i = 1}^{ℓ} | V_{i} | & = & \sum_{i = 1}^{ℓ - (a_{1} + a_{2})} | V_{i} | + \sum_{i = ℓ - (a_{1} + a_{2}) + 1}^{ℓ} | V_{i} | \\ \leq & (ℓ - a_{1} - a_{2}) ⌈ \frac{n}{2} ⌉ + a_{1} + 2 a_{2} \\ = & (ℓ - m_{1} - m_{2}) ⌈ \frac{n}{2} ⌉ + (m_{1} + 2 m_{2}) + (1 - ⌈ \frac{n}{2} ⌉) i + (2 - ⌈ \frac{n}{2} ⌉) j \\ \leq & (ℓ - m_{1} - m_{2}) ⌈ \frac{n}{2} ⌉ + (m_{1} + 2 m_{2}) - (4 i + 3 j) (because n \geq 9) \\ \leq & (ℓ - m_{1} - m_{2} - ϵ) ⌈ \frac{n}{2} ⌉ + (m_{1} + 2 m_{2} + 2 ϵ) \\ < & \frac{n (n + 1)}{2}, \end{array}$ which contradicts Fact 4.3 (1) (where $ϵ$ is 0 when $n$ is even and is 1 otherwise).
$n \geq 13$ is odd and $(a_{1}, a_{2}) = (m_{1}, m_{2})$ . Then $a_{1} = ⌊ \frac{n + 1}{4} ⌋ \geq 3$ and $a_{2} = {\begin{cases} ⌈ \frac{5 n}{12} ⌉ & if n \equiv 3 (\mod 12), \\ ⌈ \frac{5 n}{12} ⌉ + 1 & if n ≢ 3 (\mod 12) . \end{cases}$ Let $A_{1} = {V_{i} | i \in I}$ where $I = {ℓ - i | | 0 \leq i \leq ℓ - a_{1} + 1}$ . Let $z = \sum_{i, j \in I - {t}} | C N (V_{i}) \cap C N (V_{i}) |$ for some $t \in I$ . Since $| C N (V_{t}) \cap C N (V_{i}) | \geq 4$ for each $i \in I - {t}$ (by Fact 4.3 (9)) and $C N (V_{t}) \cap C N (V_{i}) \cap C N (V_{j}) = \emptyset$ for each 2-subset ${i, j} \subseteq I - {t}$ , we conclude $\begin{matrix} (4) & \begin{array}{llll} \sum_{i, j \in I} | C N (V_{i}) \cap C N (V_{j}) | & = & z + Σ_{i, j \in I - {t}} | C N (V_{i}) \cap C N (V_{j}) | \\ \geq & z + 4 (a_{1} - 1) \\ = & z + 4 (\binom{a_{1} - 1}{1}) . \end{array} \end{matrix}$

Since $z = 4 (\binom{3}{2})$ when $a_{1} = 3$ , by induction on $a_{1} \geq 3$ and (4), we will have $\begin{array}{llll} \sum_{i, j \in I} | C N (V_{i}) \cap C N (V_{j}) | & \geq & 4 (\binom{a_{1} - 1}{2}) + 4 (\binom{a_{1} - 1}{1}) \\ = & 4 (\binom{a_{1}}{2}) . \end{array}$

Hence

$\begin{array}{llll} \sum_{i = 1}^{ℓ} | C N (V_{i}) | & = & \sum_{V_{i} \in A_{2}} | C N (V_{i}) | + \sum_{V_{i} \in A_{1}} | C N (V_{i}) | \\ \leq & 4 a_{2} + (2 n - 2) a_{1} - 4 (\binom{a_{1}}{2}) \\ < & \frac{n (n + 1)}{2}, \end{array}$ which contradicts Fact 4.3 (1).
$n = 9$ and $(a_{1}, a_{2}) = (2, 5)$ . Then $ℓ = 14$ , $A_{1} = {V_{13}, V_{14}}$ and $A_{2} = {V_{i} | 8 \leq i \leq 12}$ . If $T (K_{n}) [V_{13} \cup V_{14}] ≅ K_{2}$ , then, by $| C N (V_{13}) \cup C N (V_{14}) | = 3 n - 3 = 24$ and Fact 4.3 (2,3), we have $\begin{array}{llll} | ⋃_{i = 1}^{ℓ} C N (V_{i}) | & = & | ⋃_{i \in A_{1} \cup A_{2}} C N (V_{i}) | \\ \leq & | ⋃_{i \in A_{1}} C N (V_{i}) | + | ⋃_{i \in A_{2}} C N (V_{i}) | \\ \leq & 24 + 4 a_{2} \\ = & 44 \\ < & 45 \\ = & \frac{n (n + 1)}{2}, \end{array}$ which contradicts Fact 4.3 (1). So $V_{13} \cup V_{14}$ is an independent set, and by Obsevation 4.1 (6), we may assume $V_{13} = {v_{1}}$ and $V_{14} = {e_{23}}$ , which implies $| C N (V_{13}) \cup C N (V_{14}) | = 28$ . Then the assumption $v_{1} ≻_{t} V_{12}$ implies $V_{12} = {v_{p}, e_{1 q}}$ for some $p \neq q$ by Obsevation 4.1 (6). If ${p, q} \cap {2, 3} = \emptyset$ , then each of the six numbers 4, 5, 6, 7, 8, 9 must be appeared three times in the indices of the elements of $V_{8} \cup \dots \cup V_{11}$ , which is not possible. Because the number of indices in the elements of each $V_{i} \in A_{2}$ , is at most four. So, we have ${p, q} \cap {2, 3} \neq \emptyset$ . Then the number of appearing all of the six numbers 4, 5, 6, 7, 8, 9 (by allowing repeating numbers) as indices of the elements of $V_{8} \cup \dots \cup V_{11}$ can be reduced to 16. But then we have the contradiction $e_{23} ⊁_{t} V_{k}$ for each $k$ .

Therefore $ℓ \geq ⌈ \frac{5 n}{3} ⌉$ , and in fact $χ_{d}^{t} (T (K_{n})) = ⌈ \frac{5 n}{3} ⌉$ by (3).

References:

M. A. Henning. Total dominator colorings and total domination in graphs. Graphs and Combinatorics, 31:953–974, 2015.
M. A. Henning and A. Yeo. Total domination in graphs. Springer Monographs in Mathematics. Springer, 2013. 10.1007/978-1-4614-6525-6.
P. Jalilolghadr, A. P. Kazemi, and A. Khodkar. Total dominator coloring of the circulant graphs C_n(a, b). Utilitas Mathematica, 115:105–117, 2020. 10.1051/ro/2022183.
A. P. Kazemi. Total dominator coloring in product graphs. Utilitas Mathematica, 94:329–345, 2014.
A. P. Kazemi. Total dominator chromatic number of a graph. Transactions on Combinatorics, 4(2):57–68, 2015.
A. P. Kazemi. Total dominator chromatic number of mycieleskian graphs. Utilitas Mathematica, 103:129–137, 2017.
A. P. Kazemi and F. Kazemnejad. Total dominator total chromatic numbers of cycles and paths. RAIRO-Operations Research, 57(2):383–399, 2023. 10.1051/ro/2022183.
A. P. Kazemi, F. Kazemnejad, and S. Moradi. Total mixed domination in graphs. AKCE International Journal of Graphs and Combinatorics, 19(3):229–237, 2022. 10.1080/09728600.2022.2111240.
A. P. Kazemi, F. Kazemnejad, and S. Moradi. Total dominator total coloring of a graph. Contributions to Discrete Mathematics, 18(2):1–19, 2023. 10.55016/ojs/cdm.v18i2.70912.
F. Kazemnejad and A. P. Kazemi. Total dominator coloring of central graphs. Ars Combinatoria, 155:45–67, 2021.
F. Kazemnejad, B. Pahlavsay, E. Palezzato, and M. Torielli. Total dominator coloring number of middle graphs. Discrete Mathematics, Algorithms and Applications, 15(2):2250076, 2023. http://dx.doi.org/10.1142/S1793830922500763.

[1] M. A. Henning. Total dominator colorings and total domination in graphs. Graphs and Combinatorics, 31:953–974, 2015.

[2] M. A. Henning and A. Yeo. Total domination in graphs. Springer Monographs in Mathematics. Springer, 2013. 10.1007/978-1-4614-6525-6.

[3] P. Jalilolghadr, A. P. Kazemi, and A. Khodkar. Total dominator coloring of the circulant graphs C_n(a, b). Utilitas Mathematica, 115:105–117, 2020. 10.1051/ro/2022183.

[4] A. P. Kazemi. Total dominator coloring in product graphs. Utilitas Mathematica, 94:329–345, 2014.

[5] A. P. Kazemi. Total dominator chromatic number of a graph. Transactions on Combinatorics, 4(2):57–68, 2015.

[6] A. P. Kazemi. Total dominator chromatic number of mycieleskian graphs. Utilitas Mathematica, 103:129–137, 2017.

[7] A. P. Kazemi and F. Kazemnejad. Total dominator total chromatic numbers of cycles and paths. RAIRO-Operations Research, 57(2):383–399, 2023. 10.1051/ro/2022183.

[8] A. P. Kazemi, F. Kazemnejad, and S. Moradi. Total mixed domination in graphs. AKCE International Journal of Graphs and Combinatorics, 19(3):229–237, 2022. 10.1080/09728600.2022.2111240.

[9] A. P. Kazemi, F. Kazemnejad, and S. Moradi. Total dominator total coloring of a graph. Contributions to Discrete Mathematics, 18(2):1–19, 2023. 10.55016/ojs/cdm.v18i2.70912.

[10] F. Kazemnejad and A. P. Kazemi. Total dominator coloring of central graphs. Ars Combinatoria, 155:45–67, 2021.

[11] F. Kazemnejad, B. Pahlavsay, E. Palezzato, and M. Torielli. Total dominator coloring number of middle graphs. Discrete Mathematics, Algorithms and Applications, 15(2):2250076, 2023. http://dx.doi.org/10.1142/S1793830922500763.

Contents

Utilitas Mathematica

Total dominator total chromatic numbers of some graphs

Abstract

1. Introduction

1.1. Total mixed dominating set

1.2. TD-coloring and TDT-coloring of a graph

1.3. Goal of the paper

2. Wheels

3. Complete bipartite graphs

4. Complete graphs

References:

Information

Guidelines

CP Initiatives

Follow CP