Signed strong Roman domination in graphs

Authors

  • Seyed Mahmoud Sheikholeslami
  • Rana Khoeilar
  • Leila Asgharsharghi

DOI:

https://doi.org/10.5556/j.tkjm.48.2017.2240

Keywords:

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.

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.

Downloads

Published

2017-06-30

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

Issue

Section

Papers

Most read articles by the same author(s)