## Abstract

The Roman domination number and Italian domination number (also known as the Roman {2}-domination number) are graph labeling problems in which each vertex is labeled with either 0, 1, or 2. In the Roman domination problem, each vertex labeled 0 must be adjacent to at least one vertex labeled 2. In the Italian domination problem, each vertex labeled 0 must have the labels of the vertices in its closed neighborhood sum to at least two. The Italian domination number, γ_{I}(G), of a graph G is the minimum possible sum of such a labeling, where the sum is taken over all the vertices in G. It is known that if T is a tree with at least two vertices, then γ(T)+1≤γ_{I}(T)≤2γ(T). In this paper, we characterize the trees T for which γ(T)+1=γ_{I}(T), and we characterize the trees T for which γ_{I}(T)=2γ(T).

Original language | English |
---|---|

Pages (from-to) | 557-564 |

Number of pages | 8 |

Journal | Discrete Applied Mathematics |

Volume | 217 |

DOIs | |

Publication status | Published - 30 Jan 2017 |

## Keywords

- Dominating set
- Roman {2}-dominating set
- Tree

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics