Roman domination excellent graphs: trees

Document Type : Original paper


University of Architecture, Civil Đ•ngineering and Geodesy; Department of Mathematics


A Roman dominating function (RDF) on a graph $G = (V, E)$
is a labeling $f : V rightarrow {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) = Sigma_{vin V} f(v)$
The Roman domination number, $gamma_R(G)$, of $G$ is the
minimum weight of an RDF on $G$.
An RDF of minimum weight is called a $gamma_R$-function.
A graph G is said to be $gamma_R$-excellent if for each vertex $x in V$
there is a $gamma_R$-function $h_x$ on $G$ with $h_x(x) not = 0$.
We present a constructive characterization of $gamma_R$-excellent trees using labelings.
A graph $G$ is said to be in class $UVR$ if $gamma(G-v) = gamma (G)$ for each $v in V$,
where $gamma(G)$ is the domination number of $G$.
We show that each tree in $UVR$ is $gamma_R$-excellent.


Main Subjects