Some progress on the mixed roman domination in graphs

¹ Department of Mathematics, Babol Noshirvani University of Technology, Shariati Ave., Babol 47148-71167, I.R. Iran
² Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R. Iran
³ LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria
⁴ Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, P.R. China
⁵ Department of Mathematics, University of Architecture, Civil Engineering and Geodesy, Hristo Smirnenski 1 Blv., Sofia 1046, Bulgaria

^* Corresponding author: ha.ahangar@nit.ac.ir

Received: 30 May 2018
Accepted: 15 April 2020

Abstract

Let G = (V, E) be a simple graph with vertex setxs V and edge set E. A mixed Roman dominating function of G is a function f : V ∪ E → {0, 1, 2} satisfying the condition that every element x ∈ V ∪ E for which f(x) = 0 is adjacent or incident to at least one element y ∈ V ∪ E for which f(y) = 2. The weight of a mixed Roman dominating function f is ω(f) = ∑_x∈V∪E f(x). The mixed Roman domination number γ_R(G) of G is the minimum weight of a mixed Roman dominating function of G. We first show that the problem of computing γ_R^*(G) is NP-complete for bipartite graphs and then we present upper and lower bounds on the mixed Roman domination number, some of them are for the class of trees.