Roman Bondage Numbers of Some Graphs

Original · EN

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)=∑ᵤ∈ ᵥ 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.