Roman domination in graphs: the class R_UVR

Publication date 16 September 2016

Abstract: For a graph

G = (V, E)

, a Roman dominating function

f : V i g h t a r r o w 0, 1, 2

has the property that every vertex

v i n V

with

f (v) = 0

has a neighbor

u

with

f (u) = 2

. The weight of a Roman dominating function

f

is the sum

f (V) = c u p_{v i n V} f (v)

, and the minimum weight of a Roman dominating function on

G

is the Roman domination number

g a m m a_{R} (G)

of

G

. The Roman bondage number

b_{R} (G)

of

G

is the minimum cardinality of all sets

F s u b s e t e q E

for which

g a m m a_{R} (G - F) > g a m m a_{R} (G)

. A graph

G

is in the class

m a t h c a l R_{U V R}

if the Roman domination number remains unchanged when a vertex is deleted. In this paper we obtain tight upper bounds for

g a m m a_{R} (G)

and

b_{R} (G)

provided a graph

G

is in

m a t h c a l R_{U V R}

. We present necessary and sufficient conditions for a tree to be in the class

m a t h c a l R_{U V R}

. We give a constructive characterization of

m a t h c a l R_{U V R}

-trees using labellings.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Roman domination in graphs: the class \(\mathcal{R}_{UVR}\)