Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21283120180601Roman domination excellent graphs: trees1241365410.22049/cco.2017.25806.1041ENVladimir D.SamodivkinUniversity of Architecture, Civil Đ•ngineering and Geodesy;
Department of Mathematics0000-0001-7934-5789Journal Article20161002A Roman dominating function (RDF) on a graph $G = (V, E)$ <br />is a labeling $f : V rightarrow {0, 1, 2}$ such<br />that every vertex with label $0$ has a neighbor with label $2$. <br />The weight of $f$ is the value $f(V) = Sigma_{vin V} f(v)$<br />The Roman domination number, $gamma_R(G)$, of $G$ is the<br />minimum weight of an RDF on $G$.<br />An RDF of minimum weight is called a $gamma_R$-function.<br />A graph G is said to be $gamma_R$-excellent if for each vertex $x in V$<br />there is a $gamma_R$-function $h_x$ on $G$ with $h_x(x) not = 0$. <br />We present a constructive characterization of $gamma_R$-excellent trees using labelings. <br />A graph $G$ is said to be in class $UVR$ if $gamma(G-v) = gamma (G)$ for each $v in V$, <br />where $gamma(G)$ is the domination number of $G$. <br /> We show that each tree in $UVR$ is $gamma_R$-excellent.http://comb-opt.azaruniv.ac.ir/article_13654_ec8df599ae3874367c247f6fb520698c.pdf