Samodivkin, V. (2018). Roman domination excellent graphs: trees. Communications in Combinatorics and Optimization, 3(1), 1-24. doi: 10.22049/cco.2017.25806.1041
Vladimir D. Samodivkin. "Roman domination excellent graphs: trees". Communications in Combinatorics and Optimization, 3, 1, 2018, 1-24. doi: 10.22049/cco.2017.25806.1041
Samodivkin, V. (2018). 'Roman domination excellent graphs: trees', Communications in Combinatorics and Optimization, 3(1), pp. 1-24. doi: 10.22049/cco.2017.25806.1041
Samodivkin, V. Roman domination excellent graphs: trees. Communications in Combinatorics and Optimization, 2018; 3(1): 1-24. doi: 10.22049/cco.2017.25806.1041
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.