Signed strong Roman domination in graphs

Seyed Mahmoud Sheikholeslami, Rana Khoeilar, Leila Asgharsharghi


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.


signed strong Roman dominating function, signed strong Roman domination number.

Full Text:



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.


Sponsored by Tamkang University | ISSN 0049-2930 (Print), ISSN 2073-9826 (Online) | Powered by MathJax