Independent Roman bondage of graphs

¹ Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, P.R. China
² Department of Mathematics Azarbaijan Shahid Madani University, Tabriz, I.R. Iran
³ LAMDA-RO Laboratory, Department of Mathematics, University of Blida, Blida, Algeria

^* Corresponding author: s.m.sheikholeslami@azaruniv.ac.ir

Received: 25 August 2022
Accepted: 10 February 2023

Abstract

An independent Roman dominating function (IRD-function) on a graph G is a function f : V(G) → {0, 1, 2} satisfying the conditions that (i) every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2, and (ii) the set of all vertices assigned non-zero values under f is independent. The weight of an IRD-function is the sum of its function values over all vertices, and the independent Roman domination number i_R(G) of G is the minimum weight of an IRD-function on G. In this paper, we initiate the study of the independent Roman bondage number b_iR(G) of a graph G having at least one component of order at least three, defined as the smallest size of set of edges F ⊆ E(G) for which i_R(G − F) > i_R(G). We begin by showing that the decision problem associated with the independent Roman bondage problem is NP-hard for bipartite graphs. Then various upper bounds on b_iR(G) are established as well as exact values on it for some special graphs. In particular, for trees T of order at least three, it is shown that b_iR(T) ≤ 3, while for connected planar graphs the upper bounds are in terms of the maximum degree with refinements depending on the girth of the graph.