Dehgardi, N. (2018). Mixed Roman domination and 2-independence in trees. Communications in Combinatorics and Optimization, 3(1), 79-91. doi: 10.22049/cco.2018.25964.1062

Nasrin Dehgardi. "Mixed Roman domination and 2-independence in trees". Communications in Combinatorics and Optimization, 3, 1, 2018, 79-91. doi: 10.22049/cco.2018.25964.1062

Dehgardi, N. (2018). 'Mixed Roman domination and 2-independence in trees', Communications in Combinatorics and Optimization, 3(1), pp. 79-91. doi: 10.22049/cco.2018.25964.1062

Dehgardi, N. Mixed Roman domination and 2-independence in trees. Communications in Combinatorics and Optimization, 2018; 3(1): 79-91. doi: 10.22049/cco.2018.25964.1062

Mixed Roman domination and 2-independence in trees

^{}Sirjan University of Technology, Sirjan 78137, Iran

Abstract

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.