# Total Domination number of a hypercube (Solved)

**Conjecture**For any integer , .

Here denotes the -dimensional hypercube, i.e. the graph with vertex set and two vertices adjacent if they differ in exactly one coordinate. A *total dominating set* of a graph is a set of vertices of such that every vertex has at least one neighbor in ". The *total domination number* of is the cardinality of a minimum total dominating set. A *total dominator coloring* of a graph , briefly TDC, is a proper coloring of in which each vertex of the graph is adjacent to every vertex of some color class. The *total dominator chromatic number* of is the minimum number of color classes in a TDC in (see [Kaz1]).

The following theorems are proved in [Kaz2].

**Theorem**For any integer , .

**Theorem**1. If , then .

2. If , then .

3. If , then .

**Theorem**For any integer , .

## 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.

## The conjecture is false

The conjecture is false and it can be seen that this is so by using a computer program. For example which is not a power of two.

Alternatively we can argue as follows. For any graph we clearly have Now the bound by Alon and Spencer states In particular this implies that for any constant and large enough we have