# Roman domination excellent graphs: trees

Document Type: Original paper

Author

University of Architecture, Civil Еngineering and Geodesy; Department of Mathematics

Abstract

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.

Keywords

Main Subjects