Nonnegative signed total Roman domination in graphs

DOAJ (DOAJ: Directory of Open Access Journals)

Abstract

Let $G$ be a finite and simple graph with vertex set $V(G)$. A nonnegative signed total Roman dominating function (NNSTRDF) on a graph $G$ is a function $f:V(G)\rightarrow\{-1, 1, 2\}$ satisfying the conditions that (i) $\sum_{x\in N(v)}f(x)\ge 0$ for each $v\in V(G)$, where $N(v)$ is the open neighborhood of $v$, and (ii) every vertex $u$ for which $f(u)=-1$ has a neighbor $v$ for which $f(v)=2$. The weight of an NNSTRDF $f$ is $\omega(f)=\sum_{v\in V (G)}f(v)$. The nonnegative signed total Roman domination number $\gamma^{NN}_{stR}(G)$ of $G$ is the minimum weight of an NNSTRDF on $G$. In this paper we initiate the study of the nonnegative signed total Roman domination number of graphs, and we present different bounds on $\gamma^{NN}_{stR}(G)$. We determine the nonnegative signed total Roman domination number of some classes of graphs. If $n$ is the order and $m$ is the size of the graph $G$, then we show that $\gamma^{NN}_{stR}(G)\ge \frac{3}{4}(\sqrt{8n+1}+1)-n$ and $\gamma^{NN}_{stR}(G)\ge (10n-12m)/5$. In addition, if $G$ is a bipartite graph of order $n$, then we prove that $\gamma^{NN}_{stR}(G)\ge \frac{3}{2}(\sqrt{4n+1}-1)-n$.

Authors 2

1. Nasrin Dehgardi

   Sirjan University of Technology

   Affiliation as printed

   ORCiD

   Sirjan University of Technology

   Sirjan University of Technology, Sirjan 78137, Iran

2. Lutz Volkmann Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University

   ORCiD