Strong Roman Domination Number of Complementary Prism Graphs

Year 2019, Volume: 11 Issue: 1, 40 - 47, 30.06.2019

Doost Ali Mojdeh , Ali Parsian İman Masoumi

Abstract

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}$.

Keywords

Strong Roman domination, double Roman domination, Roman domination, prism, complementary prism

References

• 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.