# On the dominator colorings in trees

• Volume: 32, Issue: 4, page 677-683
• ISSN: 2083-5892

top

## Abstract

top
In a graph G, a vertex is said to dominate itself and all its neighbors. A dominating set of a graph G is a subset of vertices that dominates every vertex of G. The domination number γ(G) is the minimum cardinality of a dominating set of G. A proper coloring of a graph G is a function from the set of vertices of the graph to a set of colors such that any two adjacent vertices have different colors. A dominator coloring of a graph G is a proper coloring such that every vertex of V dominates all vertices of at least one color class (possibly its own class). The dominator chromatic number ${\chi }_{d}\left(G\right)$ is the minimum number of color classes in a dominator coloring of G. Gera showed that every nontrivial tree T satisfies $\gamma \left(T\right)+1\le {\chi }_{d}\left(T\right)\le \gamma \left(T\right)+2$. In this note we characterize nontrivial trees T attaining each bound.

## How to cite

top

Houcine Boumediene Merouane, and Mustapha Chellali. "On the dominator colorings in trees." Discussiones Mathematicae Graph Theory 32.4 (2012): 677-683. <http://eudml.org/doc/270842>.

@article{HoucineBoumedieneMerouane2012,
abstract = {In a graph G, a vertex is said to dominate itself and all its neighbors. A dominating set of a graph G is a subset of vertices that dominates every vertex of G. The domination number γ(G) is the minimum cardinality of a dominating set of G. A proper coloring of a graph G is a function from the set of vertices of the graph to a set of colors such that any two adjacent vertices have different colors. A dominator coloring of a graph G is a proper coloring such that every vertex of V dominates all vertices of at least one color class (possibly its own class). The dominator chromatic number $χ_d(G)$ is the minimum number of color classes in a dominator coloring of G. Gera showed that every nontrivial tree T satisfies $γ(T)+1 ≤ χ_d(T) ≤ γ(T)+2$. In this note we characterize nontrivial trees T attaining each bound.},
author = {Houcine Boumediene Merouane, Mustapha Chellali},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {dominator coloring; domination; trees},
language = {eng},
number = {4},
pages = {677-683},
title = {On the dominator colorings in trees},
url = {http://eudml.org/doc/270842},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Houcine Boumediene Merouane
AU - Mustapha Chellali
TI - On the dominator colorings in trees
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 4
SP - 677
EP - 683
AB - In a graph G, a vertex is said to dominate itself and all its neighbors. A dominating set of a graph G is a subset of vertices that dominates every vertex of G. The domination number γ(G) is the minimum cardinality of a dominating set of G. A proper coloring of a graph G is a function from the set of vertices of the graph to a set of colors such that any two adjacent vertices have different colors. A dominator coloring of a graph G is a proper coloring such that every vertex of V dominates all vertices of at least one color class (possibly its own class). The dominator chromatic number $χ_d(G)$ is the minimum number of color classes in a dominator coloring of G. Gera showed that every nontrivial tree T satisfies $γ(T)+1 ≤ χ_d(T) ≤ γ(T)+2$. In this note we characterize nontrivial trees T attaining each bound.
LA - eng
KW - dominator coloring; domination; trees
UR - http://eudml.org/doc/270842
ER -

## References

top
1. [1] M. Chellali and F. Maffray, Dominator colorings in some classes of graphs, Graphs Combin. 28 (2012) 97-107, doi: 10.1007/s00373-010-1012-z. Zbl1234.05082
2. [2] R. Gera, On the dominator colorings in bipartite graphs in: Proceedings of the 4th International Conference on Information Technology: New Generations (2007) 947-952, doi: 10.1109/ITNG.2007.142.
3. [3] R. Gera, On dominator colorings in graphs, Graph Theory Notes of New York LII (2007) 25-30.
4. [4] R. Gera, S. Horton and C. Rasmussen, Dominator colorings and safe clique partitions, Congr. Numer. 181 (2006) 19-32. Zbl1113.05032
5. [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998). Zbl0890.05002
6. [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, Inc., New York, 1998). Zbl0883.00011
7. [7] O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ. 38, 1962).
8. [8] L. Volkmann, On graphs with equal domination and covering numbers, Discrete Appl. Math. 51 (1994) 211-217, doi: 10.1016/0166-218X(94)90110-4. Zbl0803.05049

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.