Roman Domination in a Tree

Xiaoxin Song, Hua Tang, Yincai Tang, and Xiaoqing Chen
College of Mathematics and Information Science, Henan University,
Kaifeng 475001, P.R. China

Abstract

A Roman dominating function on a graph G=(V, E) is a function f: V { 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 The minimum weight of a Roman dominating function on a graph G, denote by (G) is called the Roman dominating number of G. In [1], the authors propose a proposition that give a characterization of a tree T with (T)=(T)+2 where the dominating number (T)of T is the minimum cardinality of a dominating set in G. The authors thought the proof of the proposition is rather technical and omit the proof. But the Proposition is actually incorrect. In this paper, I will give six counterexamples of this proposition and introduce the correct characterization of a tree T with (T)=(T)+2and (T)=(T)+3.