Signed strong Roman domination in graphs
DOI:
https://doi.org/10.5556/j.tkjm.48.2017.2240Keywords:
signed strong Roman dominating function, signed strong Roman domination number.Abstract
Let $G=(V,E)$ be a finite and simple graph of order $n$ and maximum degree $\Delta$. A signed strong Roman dominating function (abbreviated SStRDF) on a graph $G$ is a function $f:V\to \{-1,1,2,\ldots,\lceil\frac{\Delta}{2}\rceil+1\}$ satisfying the conditions that (i) for every vertex $v$ of $G$, $\sum_{u\in N[v]} f(u)\ge 1$, where $N[v]$ is the closed neighborhood of $v$ and (ii) every vertex $v$ for which $f(v)=-1$ is adjacent to at least one vertex $u$ for which $f(u)\ge 1+\lceil\frac{1}{2}|N(u)\cap V_{-1}|\rceil$, where $V_{-1}=\{v\in V \mid f(v)=-1\}$. The minimum of the values $\sum_{v\in V} f(v)$, taken over all signed strong Roman dominating functions $f$ of $G$, is called the signed strong Roman domination number of $G$ and is denoted by $\gamma_{ssR}(G)$. In this paper we initiate the study of the signed strong Roman domination in graphs and present some (sharp) bounds for this parameter.References
H. Abdollahzadeh Ahangar, M. A. Henning, Y. Zhao, C. Lowenstein and V. Samodivkin, Signed Roman domination in graphs, J. Comb. Optim.,27(2014), 241--255.
H. Abdollahzadeh Ahangar, J. Amjadi, S.M. Sheikholeslami, L. Volkmann and Y. Zhao, Signed Roman edge domination numbers in graphs, J. Comb. Optim., 31(2016), 333--316.
E. W. Chambers, B. Kinnersley, N. Prince and D. B. West, Extremal problems for Roman domination, SIAM J. Discrete Math.23(2009), 1575--1586.
E. J. Cockayne, P. A. Dreyer Jr., S. M. Hedetniemi and S. T. Hedetniemi, Roman domination in graphs, Discrete Math., 278(2004),11--22.
P. Erdos, L. Posa, On the maximal number of disjoint circuits in a graph, Publ. Math. Debrecen, 9(1962), 3--12.
O. Favaron, H. Karami, R. Khoeilar and S. M. Sheikholeslami, On the Roman domination number of a graph, Discrete Math., 309(2009), 3447--3451.
S. M. Sheikholeslami and L. Volkmann, Signed Roman domination
number in digraphs, J. Comb. Optim., 30(2015), 456--467.
S. M. Sheikholeslami and L. Volkmann, The Roman $k$-domatic number of a graph}, Acta Math. Sinica, 27(2011), 1899--1906.