Roman domination and Mycieleki's structure in graphs.

Publication date 9 September 2013

Abstract: For a graph

G = (V, E)

, a function

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

is called Roman dominating function (RDF) if for any vertex

v

with

f (v) = 0

, there is at least one vertex

w

in its neighborhood with

f (w) = 2

. The weight of an RDF

f

of

G

is the value

f (V) = s u m_{v i n V} f (v)

. The minimum weight of an RDF of

G

is its Roman domination number and denoted by

g a m m a_{R} (G)

. In this paper, we first show that

g a m m a_{R} (G) + 1 l e q g a m m a_{R} (m u (G)) l e q g a m m a_{R} (G) + 2

, where

m u (G)

is the Mycielekian graph of

G

, and then characterize the graphs achieving equality in these bounds. Then for any positive integer

m

, we compute the Roman domination number of the

m

-Mycieleskian

m u_{m} (G)

of a special Roman graph

G

in terms on

g a m m a_{R} (G)

. Finally we present several graphs to illustrate the discussed graphs.

Recommendations

Cited in

(3)

This page was built for publication: Roman domination and Mycieleki's structure in graphs.