2011/09/19 by Hu, Fu-Tao, Xu, Ju-Ming
#05C69 #Combinatorics (math.CO) #E.1 #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.1109.3933
A Roman dominating function on a graph G=(V,E) is a function f: V→ \0,1,2\ satisfying the condition that every vertex u with f(u)=0 is adjacent to at least one vertex v with f(v)=2. The weight of a Roman dominating function is the value f(G)=∑u∈ V f(u). The Roman domination number of G is the minimum weight of a Roman dominating function on G. The Roman bondage number of a nonempty graph G is the minimum number of edges whose removal results in a graph with the Roman domination number larger than that of G. This paper determines the exact value of the Roman bondage numbers of two classes of graphs, complete t-partite graphs and (n-3)-regular graphs with order n for any n≥ 5.