Year 2019, Volume 11, Issue 1, Pages 40 - 47 2019-06-30

Strong Roman Domination Number of Complementary Prism Graphs

Doost Ali Mojdeh [1] , Ali Parsian [2] , Iman Masoumi [3]

30 44

Let $G=(V,E)$ be a simple graph  with vertex set $V=V(G)$, edge set $E=E(G)$ and from maximum degree $\Delta=\Delta(G)$. Also let
$f:V\rightarrow\{0,1,...,\lceil\frac{\Delta}{2}\rceil+1\}$ be a function that labels the vertices of $G$. Let $V_i=\{v\in V: f(v)=i\}$ for $i=0,1$ and let $V_2=V-(V_0\bigcup V_1)=\{w\in V: f(w)\geq2\}$. A function $f$ is called a strong Roman dominating function (StRDF) for $G$, if every $v\in V_0$ has a neighbor $w$, such that $w\in V_2$ and $f(w)\geq 1+\lceil\frac{1}{2}|N(w)\bigcap V_0|\rceil$. The minimum weight, $\omega(f)=f(V)=\Sigma_{v\in V} f(v)$, over all the strong Roman dominating functions of $G$, is called the strong Roman domination number of $G$ and we denote it by $\gamma_{StR}(G)$. An StRDF of minimum weight is called a $\gamma_{StR}(G)$-function. Let $\overline{G}$ be the complement of $G$. The complementary prism $G\overline{G}$ of $G$ is the graph formed from the disjoint union $G$ and $\overline{G}$ by adding the edges of a perfect matching between the corresponding vertices of $G$ and $\overline{G}$. In this paper, we investigate some properties of Roman, double Roman and strong Roman domination number of  $G\overline{G}$.
Strong Roman domination, double Roman domination, Roman domination, prism, complementary prism
  • Alhashim, A., Desormeaux, W.J., Haynes, T.W., Roman domination in complementary prisms, Australasian journal of combinatorics, 68(2)(2017), 218--228.
  • Alvarez-Ruiz, M.P., Mediavilla-Gradolph, T., Sheikholeslami, S.M., Valenzuela-Tripodoro, J.C., Yero, I.G., On the strong Roman domination number of graphs, Discrete Applied Mathematics, 231(2017), 44--59.
  • Bermudo, S., Fernau, H., Sigarreta, J.M., The differential and the Roman domination number of a graph, Applicable Analysis and Discrete Mathematics, 8(2014), 155--171.
  • Beeler, R.A., Haynesa, T.W., Hedetniemi, S.T., Double Roman domination, Discrete Applied Mathematics, 211(2016), 23--29.
  • Cockayne, E.J., Dreyer, P.A., Hedetniemi, S.M., Hedetniemi, S.T., Roman domination in graphs, Discrete Mathematics, 278(2004), 11--22.
  • Chambers, E.W., Kinnersley, B., Prince, N. , West, D.B., Extermal problems for Roman domination, SIAM J. Discret Mathematics, 23(3)(2009), 1575--1586.
  • Desormeaux, W.J., Haynes, T.W., Henning, M.A., Domination parameters of a graph and it\'s complement, Discussiones Mathematicae Graph Theory, 38(2018), 203--215.
  • Gongora, J.A., Independent Domination in Complementary Prisms, Master\'s Thesis, East Tennessee State University, 2009.
  • Haynes, T.W., Hedetniemi, S.T., Slater, P.J., Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
  • Haynes, T.W., Holmes, K.R.S., Koessler, D.R., Sewell, L., Locating-Domination in Complementary Prisms of Paths and Cycles, Congressus Numerantium, 199(2009), 45--55.
  • Haynes, T.W., Henning, M.A., Slater, P.J., van der Merwe, L.C. , The complementary product of two graphs, Bulletin of the Institute of Combinatorics and its Applications, 51(2007), 21--30.
  • Haynes, T.W., Henning, M.A., van der Merwe, L.C., Domination and total domination in complemantary prisms, Journal of Combinatorial Optimization, 18(2009), 23--37.
  • Janseana, P., Ananchuen, N., Matching extension in complementary prism of regular graphs, Italian Journal of Pure and Applied Mathematics, 37(2017), 553--564.
  • Lewis, J.R., Differentials of Graphs, Master\'s Thesis, East Tennessee State University, 2004.
  • Mojdeh, D.A., Parsian, A., Masoumi, I., Characterization of double Roman trees, to appear in Ars Combinatoria, (2018).
  • West, D.B., Introduction to Graph theory, Second edition, Prentice Hall, USA, 2001.
Primary Language en
Subjects Engineering
Journal Section Articles
Authors

Author: Doost Ali Mojdeh
Institution: University of Mazandaran
Country: Iran


Orcid: 0000-0001-6323-5956
Author: Ali Parsian
Institution: University of Tafresh
Country: Iran


Author: Iman Masoumi (Primary Author)
Institution: University of Tafresh
Country: Iran


Dates

Publication Date: June 30, 2019

Bibtex @research article { tjmcs474945, journal = {Turkish Journal of Mathematics and Computer Science}, issn = {}, eissn = {2148-1830}, address = {Matematikçiler Derneği}, year = {2019}, volume = {11}, pages = {40 - 47}, doi = {}, title = {Strong Roman Domination Number of Complementary Prism Graphs}, key = {cite}, author = {Mojdeh, Doost Ali and Parsian, Ali and Masoumi, Iman} }
APA Mojdeh, D , Parsian, A , Masoumi, I . (2019). Strong Roman Domination Number of Complementary Prism Graphs. Turkish Journal of Mathematics and Computer Science, 11 (1), 40-47. Retrieved from http://dergipark.org.tr/tjmcs/issue/46614/474945
MLA Mojdeh, D , Parsian, A , Masoumi, I . "Strong Roman Domination Number of Complementary Prism Graphs". Turkish Journal of Mathematics and Computer Science 11 (2019): 40-47 <http://dergipark.org.tr/tjmcs/issue/46614/474945>
Chicago Mojdeh, D , Parsian, A , Masoumi, I . "Strong Roman Domination Number of Complementary Prism Graphs". Turkish Journal of Mathematics and Computer Science 11 (2019): 40-47
RIS TY - JOUR T1 - Strong Roman Domination Number of Complementary Prism Graphs AU - Doost Ali Mojdeh , Ali Parsian , Iman Masoumi Y1 - 2019 PY - 2019 N1 - DO - T2 - Turkish Journal of Mathematics and Computer Science JF - Journal JO - JOR SP - 40 EP - 47 VL - 11 IS - 1 SN - -2148-1830 M3 - UR - Y2 - 2019 ER -
EndNote %0 Turkish Journal of Mathematics and Computer Science Strong Roman Domination Number of Complementary Prism Graphs %A Doost Ali Mojdeh , Ali Parsian , Iman Masoumi %T Strong Roman Domination Number of Complementary Prism Graphs %D 2019 %J Turkish Journal of Mathematics and Computer Science %P -2148-1830 %V 11 %N 1 %R %U
ISNAD Mojdeh, Doost Ali , Parsian, Ali , Masoumi, Iman . "Strong Roman Domination Number of Complementary Prism Graphs". Turkish Journal of Mathematics and Computer Science 11 / 1 (June 2019): 40-47.
AMA Mojdeh D , Parsian A , Masoumi I . Strong Roman Domination Number of Complementary Prism Graphs. TJMCS. 2019; 11(1): 40-47.
Vancouver Mojdeh D , Parsian A , Masoumi I . Strong Roman Domination Number of Complementary Prism Graphs. Turkish Journal of Mathematics and Computer Science. 2019; 11(1): 47-40.