Strong Roman Domination Number of Complementary Prism Graphs

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

1. Alhashim, A., Desormeaux, W.J., Haynes, T.W., Roman domination in complementary prisms, Australasian journal of combinatorics, 68(2)(2017), 218--228.
2. 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.
3. 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.
4. Beeler, R.A., Haynesa, T.W., Hedetniemi, S.T., Double Roman domination, Discrete Applied Mathematics, 211(2016), 23--29.
5. Cockayne, E.J., Dreyer, P.A., Hedetniemi, S.M., Hedetniemi, S.T., Roman domination in graphs, Discrete Mathematics, 278(2004), 11--22.
6. Chambers, E.W., Kinnersley, B., Prince, N. , West, D.B., Extermal problems for Roman domination, SIAM J. Discret Mathematics, 23(3)(2009), 1575--1586.
7. 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.
8. Gongora, J.A., Independent Domination in Complementary Prisms, Master\'s Thesis, East Tennessee State University, 2009.

9. Haynes, T.W., Hedetniemi, S.T., Slater, P.J., Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
10. 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.
11. 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.
12. 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.
13. Janseana, P., Ananchuen, N., Matching extension in complementary prism of regular graphs, Italian Journal of Pure and Applied Mathematics, 37(2017), 553--564.
14. Lewis, J.R., Differentials of Graphs, Master\'s Thesis, East Tennessee State University, 2004.
15. Mojdeh, D.A., Parsian, A., Masoumi, I., Characterization of double Roman trees, to appear in Ars Combinatoria, (2018).
16. West, D.B., Introduction to Graph theory, Second edition, Prentice Hall, USA, 2001.