Home » Subject » Graph Theory » Coloring » Vertex coloring

Total Dominator Chromatic Number of a Hypercube (Solved)

Importance: Medium ✭✭
Author(s): Adel P. Kazemi
Subject: Graph Theory
» Coloring
» » Vertex coloring
Keywords: Total dominator chromatic number, hypercube.
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 $.

Bibliography

[Kaz1] Adel P. Kazemi, Total dominator chromatic number of a graph, http://arxiv.org/abs/1307.7486.

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


* indicates original appearance(s) of problem.
add new comment

False

On November 1st, 2014 azi says:

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 http://www.openproblemgarden.org/op/total_domination_number_of_a_hypercube

reply

Comment viewing options

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