February 9, 2023
Doost Ali Mojdeh

Doost Ali Mojdeh

Degree: Professor
Address: Department of Mathematics, University of Mazandaran, Babolsar, Iran
Education: Ph.D in Mathematics (Graph Theory and Combinatorics)
Phone: 011-35302448
Faculty: Faculty of Mathematical Sciences


Title Roman 2-bondage number of a graph
Type Article
domination, Roman {2}-domination, Roman {2}-bondage number
Journal Discussiones Mathematicae Graph Theory
DOI doi:10.7151/dmgt.2144
Researchers Ahmad Moradi (First researcher) , Doost Ali Mojdeh (Second researcher) , Omid Sharifi (Third researcher)


For a given graph G = (V,E), a Roman {2}-dominating function f:V(G)→ {0,1,2} has the property that for every vertex u with f(u)=0, either u is adjacent to a vertex assigned 2 under f, or is adjacent to at least two vertices assigned 1 under f. The Roman {2}-domination number of G, γ{R2}(G), is the minimum of ∑u ∈V(G) f(u) over all such functions. In this paper, we initiate the study of the problem of finding Roman {2}-bondage number of G. The Roman {2}-bondage number of G, b{R2}, is defined as the cardinality of a smallest edge set E\prime ⊆ E for which γ{R2}(G-E\prime)>γ{R2}(G). We first demonstrate complexity status of the problem by proving that the problem is NP-Hard. Then, we derive useful parametric as well as fixed upper bounds on the Roman {2}-bondage number of G. Specifically, it is known that the Roman bondage number of every planar graph does not exceed 15 (see [S. Akbari, M. Khatirinejad and S. Qajar, A note on the Roman bondage number of planar graphs, {Graphs Combin.} {29} (2013) {327--331}]). We show that same bound will be preserved while computing the Roman {2}-bondage number of such graphs. The paper is then concluded by computing exact value of the parameter for some classes of graphs.