‎$s$-dominating function‎

‎Let $r\geq 2$. A subset $S$ of vertices of a graph $G$ is a $r$-hop independent dominating set if every vertex outside $S$ is at distance $r$ from a vertex of $S$, and for any pair $v, w\in S$, $d(v, w)\neq r$. A $r$-hop Roman dominating function ($r$HRDF) is a function $f$ on $V(G)$ with values $0,1$ and $2$ having the property that for every vertex $v \in V$ with $f(v) = 0$ there is a vertex $u$ with $f(u)=2$ and $d(u,v)=r$. A $r$-step Roman dominating function ($r$SRDF) is a function $f$ on $V(G)$ with values $0,1$ and $2$ having the property that for every vertex $v$ with $f(v)=0$ or $2$, there is a vertex $u$ with $f(u)=2$ and $d(u,v)=r$. A $r$HRDF $f$ is a $r$-hop Roman independent dominating function if for any pair $v, w$ with non-zero labels under $f$, $d(v, w)\neq r$. We show that the decision problem associated with each of $r$-hop independent domination, $r$-hop Roman domination, $r$-hop Roman independent domination and $r$-step Roman domination is NP-complete even when restricted to planar bipartite graphs or planar chordal graphs.

Let $G=(V, E)$ be a simple graph with vertex set $V$ and edge set $E$. A {\em total Roman dominating function} on a graph $G$ is a function $f:V\rightarrow \{0,1,2\}$ satisfying the following conditions: (i) every vertex $u$ {\color{blue}such that} $f(u)=0$ is adjacent to at least one vertex $v$ {\color{blue}such that} $f(v)=2$ and (ii) the subgraph of $G$ induced by the set of all vertices of positive weight has no isolated vertex. The weight of a total Roman dominating function $f$ is the value, $f(V)=\Sigma_{u\in V(G)}f(u)$. The {\em total Roman domination number} $\gamma_{tR}(G)$ of $G$ is the minimum weight of a total Roman dominating function of $G$. A subset $S$ of $V$ is a $2$-independent set of $G$ if every vertex of $S$ has at most one neighbor in $S$. The maximum cardinality of a $2$-independent set of $G$ is the $2$-independence number $\beta_2(G)$. These two parameters are incomparable in general, however, we show that if $T$ is a tree, then $\gamma_{tR}(T)\le \frac{3}{2}\beta_2(T)$ and we characterize all trees attaining the equality.

An independent Italian dominating function (IID-function) on a graph $G$ is a function $f:V(G)rightarrow{0,1,2}$ satisfying the conditions that (i) $sum_{uin N(v)}f(u)geq2$ when $f(v)=0$, and (ii) the set of all vertices assigned non-zero values under $f$ is independent. The weight of an IID-function is the sum of its function values over all vertices, and the independent Italian domination number $i_{I}(G)$ of $G$ is the minimum weight of an IID-function on $G$. In this paper, we initiate the study of the independent Italian bondage number $b_{iI}(G)$ of a graph $G$ having at least one component of order at least three, defined as the smallest size of a set of edges of $G$ whose removal from $G$ increases $i_{I}(G)$. We show that the decision problem associated with the independent Italian bondage problem is NP-hard for arbitrary graphs. Moreover, various upper bounds on $b_{iI}(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_{iI}(T)leq2$.

Let $G=(V,E)$ be a graph.  A double Roman dominating function  (DRDF) of   $G $   is a function   $f:Vto {0,1,2,3}$  such that, for each $vin V$ with $f(v)=0$,  there is a vertex $u $  adjacent to $v$  with $f(u)=3$ or there are vertices $x$ and $y $  adjacent to $v$  such that  $f(x)=f(y)=2$ and for each $vin V$ with $f(v)=1$,  there is a vertex $u $    adjacent to $v$    with  $f(u)>1$.  The weight of a DRDF $f$ is   $ f (V) =sum_{ vin V} f (v)$.   Let $n$ and  $k$ be integers such that  $3leq 2k+ 1  leq n$.  The   generalized Petersen graph $GP (n, k)=(V,E) $  is the  graph  with  $V={u_1, u_2,ldots,  u_n}cup{v_1, v_2,ldots, v_n}$ and $E={u_iu_{i+1}, u_iv_i, v_iv_{i+k}:  1 leq i leq n}$, where  addition is taken  modulo $n$. In this paper,  we firstly   prove that the  decision     problem  associated with   double Roman domination is NP-omplete even restricted to planar bipartite graphs with maximum degree at most 4.  Next, we   give  a dynamic programming algorithm for  computing a minimum DRDF (i.e., a  DRDF   with minimum weight  along  all   DRDFs)  of $GP(n,k )$  in $O(n81^k)$ time and space  and so a  minimum DRDF  of $GP(n,O(1))$  can be computed in $O( n)$ time and space.

For a graph $G=(V,E)$, a triple Roman dominating function (3RD-function) is a function $f:Vto {0,1,2,3,4}$ having the property that (i) if $f(v)=0$ then $v$ must have either one neighbor $u$ with $f(u)=4$, or two neighbors $u,w$ with $f(u)+f(w)ge 5$ or three neighbors $u,w,z$ with $f(u)=f(w)=f(z)=2$, (ii) if $f(v)=1$ then $v$ must have one neighbor $u$ with $f(u)ge 3$ or two neighbors $u,w$ with $f(u)=f(w)=2$, and (iii) if $f(v)=2$ then $v$ must have one neighbor $u$ with $f(u)ge 2$. The weight of a 3RDF $f$ is the sum $f(V)=sum_{vin V} f(v)$, and the minimum weight of a 3RD-function on $G$ is the triple Roman domination number of $G$, denoted by $gamma_{[3R]}(G)$. In this paper, we prove that for any connected graph $G$ of order $n$ with minimum degree at least two,  $gamma_{[3R]}(G)leq frac{3n}{2}$.

Let $G=(V,E)$ be a given graph of order $n $. A function $f : V to {0,1, 2}$ is an independent Roman dominating function (IRDF) on $G$ if for every vertex $vin V$ with $f(v)=0$ there is a vertex $u$ adjacent to $v$ with $f(u)=2$ and ${vin V:f(v)> 0}$ is an independent set. The weight of an IRDF $f$ on $G $ is the value $f(V)=sum_{vin V}f(v)$. The minimum weight of an IRDF among all IRDFs on $G$ is called the independent Roman domination number of~$G$. In this paper, we give algorithms for computing the independent Roman domination number of $G$ in $O(|V|)$ time when $G=(V,E)$ is a tree, unicyclic graph or proper interval graph.

‎A perfect Roman dominating function (PRDF) on a graph $G$ is a function $ f:V(G)to {0,1,2}$ satisfying the condition that every vertex $u$ with $f(u) = 0$ is adjacent to exactly one vertex $v$ for which $f(v) = 2$‎. ‎The weight of a PRDF $f$ is the sum of the weights of the vertices under $f$‎. ‎The perfect Roman domination number of $G$ is the minimum weight of a PRDF in $G$‎. ‎In this paper we study algorithmic and computational complexity aspects of the minimum perfect Roman domination problem (MPRDP)‎. ‎We first correct the proof of a result published in [Bulletin‎‎Iran‎. ‎Math‎. ‎Soc‎. ‎14(2020)‎, ‎342--351]‎, ‎and using a similar argument‎, ‎show that MPRDP is APX-hard for graphs with bounded degree 4‎.‎We prove that the decision problem associated to MPRDP is NP-complete even when restricted to star convex bipartite graphs‎. ‎Moreover‎, ‎we show that MPRDP is solvable in linear time for bounded tree-width‎‎graphs‎. ‎We also show that the perfect domination problem and perfect Roman domination problem are not equivalent in computational complexity aspects‎. ‎Finally we propose an integer linear programming formulation for MPRDP‎.

‎‎For an integer $kgeq 2$‎, ‎a Roman $k$-tuple dominating function‎, ‎(or just RkDF)‎, ‎in a graph $G$ is a function $f colon V(G) rightarrow {0‎, ‎1‎, ‎2}$ satisfying the condition that every vertex $u$ for which $f(u) = 0$ is adjacent to at least $k$ vertices $v$ for which $f(v) = 2$‎, ‎and every vertex $u$ for which $f(u) neq 0$ is adjacent to at least $k-1$ vertices $v$ for which $f(v) = 2$‎. ‎The Roman $k$-tuple domination number of ‎$‎G‎$‎‎ ‎is the minimum weight of an RkDF in $G$. ‎In this note we settle two problems posed in [Roman $k$-tuple Domination in Graphs‎, ‎Iranian J‎. ‎Math‎. ‎Sci‎. ‎Inform‎. ‎15 (2020)‎, ‎101--115]‎.

‎Let G be a graph‎. ‎A 2-rainbow dominating function (or‎ 2-RDF) of G is a function f from V(G)‎ ‎to the set of all subsets of the set {1,2}‎ ‎such that for a vertex v ∈ V (G) with f(v) = ∅, ‎the‎‎condition $bigcup_{uin N_{G}(v)}f(u)={1,2}$ is fulfilled‎, wher NG(v)  is the open neighborhood‎‎of v‎. ‎The weight of 2-RDF f of G is the value‎‎$omega (f):=sum _{vin V(G)}|f(v)|$‎. ‎The 2-rainbow‎‎domination number of G‎, ‎denoted by Υr2 (G)‎, ‎is the‎‎minimum weight of a 2-RDF of G‎. ‎A 2-RDF f is called an outer independent 2-rainbow dominating function ‎(or OI2-RDF) of G if‎‎the set of all v ∈ V (G) with f(v) = ∅ is an‎ ‎independent set‎. ‎The outer independent 2-rainbow domination number Υoir2  (G) is‎‎the minimum weight of an OI2-RDF of G‎. ‎In this paper‎, ‎we obtain the‎‎outer independent 2-rainbow domination number of Pm□Pn‎ ‎and‎ Pm□Cn‎. ‎Also we determine the value of Υoir2  (Cm2Cn) when m or n is even‎.

‎A  2-rainbow dominating function (2RDF) of a graph $G$ is a‎ ‎function $f$ from the vertex set $V(G)$ to the set of all subsets‎ ‎of the set ${1,2}$ such that for any vertex $vin V(G)$ with‎ ‎$f(v)=emptyset$ the condition $bigcup_{uin N(v)}f(u)={1,2}$‎ ‎is fulfilled‎, ‎where $N(v)$ is the open neighborhood of $v$‎. ‎A ‎ ‎maximal 2-rainbow dominating function of a graph $G$ is a ‎‎$‎‎2‎$‎-rainbow dominating function $f$ such that the set ${win‎‎V(G)|f(w)=emptyset}$ is not a dominating set of $G$‎. ‎The‎ ‎weight of a maximal 2RDF $f$ is the value $omega(f)=sum_{vin‎ ‎V}|f (v)|$‎. ‎The  maximal $2$-rainbow domination number of a‎ ‎graph $G$‎, ‎denoted by $gamma_{m2r}(G)$‎, ‎is the minimum weight of a‎ ‎maximal 2RDF of $G$‎. ‎In this paper‎, ‎we continue the study of maximal‎ ‎2-rainbow domination {number} in graphs‎. ‎Specially‎, ‎we first characterize all graphs with large‎ ‎maximal 2-rainbow domination number‎. ‎Finally‎, ‎we determine the maximal ‎$‎2‎$‎‎-‎rainbow domination number in the sun and sunlet graphs‎.

Let G=(V,E) be a graph and let f:V(G)→{0,1,2} be a function‎. ‎A vertex v is protected with respect to f‎, ‎if f(v)>0 or f(v)=0 and v is adjacent to a vertex of positive weight‎. ‎The function f is a co-Roman dominating function‎, ‎abbreviated CRDF if‎: ‎(i) every vertex in V is protected‎, ‎and (ii) each u∈V with positive weight has a neighbor v∈V with f(v)=0 such that the function f_uv:V→{0,1,2}‎, ‎defined by f_uv (v)=1‎, ‎f_uv (u)=f(u)-1 and f_uv (x)=f(x)for x∈V-{v,u}‎, ‎has no unprotected vertex‎. ‎The weight of f is ω(f)=∑_(v∈V)▒〖f(v)〗‎. ‎The co-Roman domination number of a graph G ‎, ‎denoted by γ_cr G)‎, ‎is the minimum weight of a co-Roman dominating function on G ‎. ‎In this paper, we first present an upper bound on the co-Roman domination number of trees in terms of order, the number of leaves and supports‎. Then we find bounds on the co-Roman domination number of a graph and its other dominating parameters .

‎Let $G=(V,E)$ be a graph‎. ‎A subset $Ssubset V$ is a hop dominating set‎‎if every vertex outside $S$ is at distance two from a vertex of‎‎$S$‎. ‎A hop dominating set $S$ which induces a connected subgraph‎ ‎is called a connected hop dominating set of $G$‎. ‎The‎‎connected hop domination number of $G$‎, ‎$ gamma_{ch}(G)$,‎‎‎ ‎is the minimum cardinality of a connected hop‎‎dominating set of $G$‎. ‎A hop‎‎Roman dominating function (HRDF) of a graph $G$ is a function $‎‎f‎: ‎V(G)longrightarrow {0‎, ‎1‎, ‎2} $ having the property that‎‎for every vertex $ v in V $ with $ f(v) = 0 $ there is a‎‎vertex $ u $ with $ f(u)=2 $ and $ d(u,v)=2 $‎.‎The weight of‎‎an HRDF $ f $ is the sum $f(V) = sum_{vin V} f(v) $‎. ‎The‎‎minimum weight of an HRDF on $ G $ is called the hop Roman‎‎domination number of $ G $ and is denoted by $ gamma_{hR}(G)‎‎$‎. ‎We give an algorithm‎‎that decides whether $gamma_{hR}(T)=2gamma_{ch}(T)$ for a given‎‎tree $T$.‎‎{bf Keywords:} hop dominating set‎, ‎connected hop dominating set‎, ‎hop Roman dominating‎‎function‎.

Let $G$ be a graph‎. ‎A function $f‎ : ‎V (G) longrightarrow {0,1}$‎, ‎satisfying‎ ‎the condition that every vertex $u$ with $f(u) = 0$ is adjacent with at‎ ‎least one vertex $v$ such that $f(v) = 1$‎, ‎is called a dominating function $(DF)$‎. ‎The weight of $f$ is defined as $wet(f)=Sigma_{v in V(G)} f(v)$‎. ‎The minimum weight of a dominating function of $G$‎ ‎is denoted by‎ ‎$gamma (G)$‎, ‎and is called the domination number of $G$‎. ‎A dominating‎ ‎function $f$ is called a global dominating function $(GDF)$ if $f$ is‎ ‎also a $DF$ of $overline{G}$‎. ‎The minimum weight of a global dominating function is denoted by‎ ‎$gamma_{g}(G)$ and is called global domination number of $G$‎. ‎In this paper we introduce a generalization of global dominating function‎. ‎Suppose $G$ is a graph and $sgeq 2$ and $K_n$ is the complete graph on $V(G)$‎. ‎A function $ f:V(G)longrightarrow { 0,1} $ on $G$ is $s$-dominating function $(s-DF)$‎, ‎if there exists some factorization ${G_1,ldots,G_s }$ of $K_n$‎, ‎such that $G_1=G$ and $f$ is dominating function of each $G_i$‎.

‎‎Let $G=(V‎, ‎E)$ be a simple graph with vertex set $V$ and edge set $E$‎. ‎A {em mixed Roman dominating function} (MRDF) of $G$ is a function $f:Vcup Erightarrow {0,1,2}$ satisfying the condition that every element $xin Vcup E$ for which $f(x)=0$ is adjacent‎ ‎or incident to at least one element $yin Vcup E$ for which $f(y)=2$‎. ‎The weight of an‎ ‎MRDF $f$ is $sum _{xin Vcup E} f(x)$‎. ‎The mixed Roman domination number $gamma^*_R(G)$ of $G$ is‎ ‎the minimum weight among all mixed Roman dominating functions of $G$‎. ‎A subset $S$ of $V$ is a 2-independent set of $G$ if every vertex of $S$ has at most one neighbor in $S$‎. ‎The minimum cardinality of a 2-independent set of $G$ is the 2-independence number $beta_2(G)$‎. ‎These two parameters are incomparable in general‎, ‎however‎, ‎we show that if $T$ is a tree‎, ‎then $frac{4}{3}beta_2(T)ge gamma^*_R(T)$ and we characterize all trees attaining the equality‎.

A {em Roman dominating function} on a graph $G$ is a function $f:V(G)rightarrow {0,1,2}$ satisfying the condition that every vertex $u$ for which $f(u) = 0$ is adjacent to at least one vertex $v$ for which $f(v) =2$. {color{blue}A {em restrained Roman dominating} function} $f$ is a {color{blue} Roman dominating function if the vertices with label 0 induce a subgraph with no isolated vertex.} The weight of a restrained Roman dominating function is the value $omega(f)=sum_{uin V(G)} f(u)$. The minimum weight of a restrained Roman dominating function of $G$ is called the { em restrained Roman domination number} of $G$ and denoted by $gamma_{rR}(G)$. In this paper we establish some sharp bounds for this parameter.

A function $f:V(G)rightarrow {-1,0,1}$ is a {em minus dominating function} if for every vertex $vin V(G)$, $sum_{uin N[v]}f(u)ge 1$. A minus dominating function $f$ of $G$ is called a {em global minus dominating function} if $f$ is also a minus dominating function of the complement $overline{G}$ of $G$. The {em global minus domination number} $gamma_{g}^-(G)$ of $G$ is defined as $gamma_{g}^-(G)=min{sum_{vin V(G)} f(v)mid f mbox{is a global minus dominating function of} G}$. In this paper we initiate the study of global minus domination number in graphs and we establish lower and upper bounds for the global minus domination number.