Roman Bondage Number of a Graph

Publication date 18 September 2011

Abstract: The Roman dominating function on a graph

G = (V, E)

is a function

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

such that each vertex

x

with

f (x) = 0

is adjacent to at least one vertex

y

with

f (y) = 2

. The value

f (G) = s u m l i m i t s_{u i n V (G)} f (u)

is called the weight of

f

. The Roman domination number

g a m m a_{m R} (G)

is defined as the minimum weight of all Roman dominating functions. This paper defines the Roman bondage number

b_{m R} (G)

of a nonempty graph

G = (V, E)

to be the cardinality among all sets of edges

B s u b s e t e q E

for which

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

. Some bounds are obtained for

b_{m R} (G)

, and the exact values are determined for several classes of graphs. Moreover, the decision problem for

b_{m R} (G)

is proved to be NP-hard even for bipartite graphs.

This page was built for publication: Roman Bondage Number of a Graph