Roman Bondage Number of a Graph

2011/09/19 by Hu, Fu-Tao, Xu, Jun-Ming
#05C69 #Combinatorics (math.CO) #E.1 #FOS: Mathematics #G.2.2

paper · doi:10.48550/arxiv.1109.3930

Abstract

The Roman dominating function on a graph G=(V,E) is a function f: V→\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)=∑_{u∈ V(G)} f(u) is called the weight of f. The Roman domination number γ_{\rm R}(G) is defined as the minimum weight of all Roman dominating functions. This paper defines the Roman bondage number b_{\rm R}(G) of a nonempty graph G=(V,E) to be the cardinality among all sets of edges B⊆ E for which γ_{\rm R}(G-B)>γ_{\rm R}(G). Some bounds are obtained for b_{\rm R}(G), and the exact values are determined for several classes of graphs. Moreover, the decision problem for b_{\rm R}(G) is proved to be NP-hard even for bipartite graphs.

Related

• On the Roman bondage number of a graph
• Roman Bondage Numbers of Some Graphs
• On The Double Roman bondage numbers of Graphs
• On the Roman Bondage Number of Graphs on surfaces
• Roman domination in graphs: the class R_UV R