Signed strong Roman domination in graphs

Main Article Content

Seyed Mahmoud Sheikholeslami
Rana Khoeilar
Leila Asgharsharghi

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.

Article Details

How to Cite
Sheikholeslami, S. M., Khoeilar, R., & Asgharsharghi, L. (2017). Signed strong Roman domination in graphs. Tamkang Journal of Mathematics, 48(2), 135–147. https://doi.org/10.5556/j.tkjm.48.2017.2240
Section
Papers
Author Biographies

Seyed Mahmoud Sheikholeslami

Department ofMathematics, Azarbaijan ShahidMadani University, Tabriz, I.R. Iran.

Rana Khoeilar

Department ofMathematics, Azarbaijan ShahidMadani University, Tabriz, I.R. Iran.

Leila Asgharsharghi

Department ofMathematics, Azarbaijan ShahidMadani University, Tabriz, I.R. Iran.

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.

Most read articles by the same author(s)

Similar Articles

You may also start an advanced similarity search for this article.