Roman Domination in a Tree

Abstract

A Roman dominating function on a graph \(G = (V, E)\) is a function \(f : V \rightarrow \{0, 1, 2\}\) satisfying the condition that every vertex \(u\) for which \(f(u) = 0\) is adjacent to at least one vertex \(v\) for which \(f(v) = 2\). The weight of a Roman dominating function is the value \(f(V) = \sum_{u \in V} f(u)\). The minimum weight of a Roman dominating function on a graph \(G\), denoted by \(\gamma_R(G)\), is called the Roman domination number of \(G\). In [E.J. Cockayne, P.A. Dreyer, Jr.,S.M. Hedetniemi, S.T. Hedetniemi, Roman domination in graphs,Discrete Math. \(278(2004) 11-22.]\), the authors stated a proposition which characterized trees which satisfy \(\gamma_R(T) = \gamma(T) + 2\), where \(\gamma(T)\) is the domination number of \(T\). The authors thought the proof of the proposition was rather technical and chose to omit its proof; however, the proposition is actually incorrect. In this paper, we will give a counterexample of this proposition and introduce the correct characterization of a tree \(T\) with \(\gamma_R(T) = \gamma(T) + 2\).