roman domination excellent graphs: trees

A roman dominating function (rdf) on a graph g=(v,e) is a labeling f:v→{0,1,2} such that every vertex with label 0 has a neighbor with label 2. the weight of f is the value f(v)=σv∈vf(v) the roman domination number, γr(g), of g is the minimum weight of an rdf on g. an rdf of minimum weight is called a γr-function. a graph g is said to be γr-excellent if for each vertex x∈v there is a γr-function hx on g with hx(x)≠0. we present a constructive characterization of γr-excellent trees using labelings. a graph g is said to be in class uvr if γ(g−v)=γ(g) for each v∈v, where γ(g) is the domination number of g. we show that each tree in uvr is γr-excellent.