Total Dominator Chromatic Number of a Hypercube (Solved)

Importance: Medium ✭✭
Author(s): Adel P. Kazemi
Recomm. for undergrads: no
Posted by: Adel P. Kazemi
on: October 6th, 2013
Solved by: See comment.
Conjecture   For any integer $ n\geq 5 $, $ \chi_d^t(Q_n)=2^{n-2}+2 $.

Here $  Q_n  $ denotes the $ n $-dimensional hypercube, i.e. the graph with vertex set $  \{0,1\}^n  $ and two vertices adjacent if they differ in exactly one coordinate. A total dominator coloring of a graph $ G $, briefly TDC, 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 $ \chi_d^t(G) $ of $ G $ is the minimum number of color classes in a TDC in $ G $ (see [Kaz1]). A total dominating set of a graph $ G $ is a set $ S $ of vertices of $ G $ such that every vertex has at least one neighbor in $ S $". The total domination number $ \gamma_t(G) $ of $ G $ is the cardinality of a minimum total dominating set.

The following theorems are proved in [Kaz2].

Theorem   For any integer $ n\geq 4 $, $ \gamma_t(Q_n)\leq2^{n-2} $.
Theorem   For any integer $ n\geq 1 $, $ \gamma_t(Q_n) \leq \chi_d^t(Q_n) \leq \gamma_t(Q_n)+ 2 $.
Theorem   1. If $ n=1 $, then $ \chi_d ^t(Q_n)=2^n $.
2. If $ n=2,3 $, then $ \chi_d ^t(Q_n)=2^{n-1} $.
3. If $ n=4 $, then $ \chi_d ^t(Q_n)=2^{n-2}+2 $.


[Kaz1] Adel P. Kazemi, Total dominator chromatic number of a graph,

[Kaz2] Adel P. Kazemi, Total Dominator Coloring in Product Graphs, Utilitas Mathematica (2013), Accepted.

* indicates original appearance(s) of problem.


Since $ \chi^t_d(G) \leq \chi(G)+ \gamma(G) $ it follows that for large enough $ n $ the conjecture does not hold by the same token as written in the comment here

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.