Weak Roman domination stable graphs upon edge-addition

Document Type : Original paper

Authors

1 University of Madras

2 DEPARTMENT OF MATHEMATICS DHANRAJ BAID JAIN COLLEGE

Abstract

A Roman dominating function (RDF) on a graph $G$ is a function $f: V(G) \to \{0, 1, 2\}$ such that every vertex with label 0 has a neighbor with label 2. A vertex $u$ with $f(u)=0$ is said to be undefended if it is not adjacent to a vertex with $f(v)>0$. The function $f:V(G) \to \{0, 1, 2\}$ is a weak Roman dominating function (WRDF) if each vertex $u$ with $f(u) = 0$ is adjacent to a vertex $v$ with $f(v) > 0$ such that the function $f^{\prime}: V(G) \to \{0, 1, 2\}$ defined by $f^{\prime}(u) = 1$, $f^{\prime}(v) = f(v) - 1$ and $f^{\prime}(w) = f(w)$ if $w \in V - \{u, v\}$, has no undefended vertex. A graph $G$ is said to be Roman domination stable upon edge addition, or just $\gamma_R$-EA-stable, if $\gamma_R(G+e)= \gamma_R(G)$ for any edge $e \notin E(G)$. We extend this concept to a weak Roman dominating function as follows: A graph $G$ is said to be weak Roman domination stable upon edge addition, or just $\gamma_r$-EA-stable, if $\gamma_r(G+e)= \gamma_r(G)$ for any edge $e \notin E(G)$. In this paper, we study $\gamma_r$-EA-stable graphs, obtain bounds for  $\gamma_r$-EA-stable graphs and  characterize $\gamma_r$-EA-stable trees which attain the bound. 

Keywords

Main Subjects

References

[1] M. Chellali and N. Jafari Rad, Roman domination stable graphs upon edge-addition, Util. Math. 96 (2015), 165–178.
[2] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Roman domination in graphs, Topics in Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer, Berlin/Heidelberg, 2020, pp. 365–409.
[3] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, A survey on Roman domination parameters in directed graphs, J. Combin. Math. Combin. Comput. 115 (2020), 141–171.
[4] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Comb. 17 (2020), no. 3, 966–984.
[5] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination, Structures of Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer, Berlin/Heidelberg, 2021, pp. 273–307.
[6] E.J. Cockayne, P.A. Dreyer Jr, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1-3, 11–22.
[7] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs; Advanced Topics, Marcel Dekker, Inc., New York, 1998.
[8] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York,
1998.
[9] M.A. Henning and S.T. Hedetniemi, Defending the Roman empire–A new strategy, Discrete Math. 266 (2003), no. 1-3, 239–251.
[10] P. Roushini Leely Pushpam and M Kamalam, Efficient weak Roman domination in graphs, Int. J. Pure Appl. Math. 101 (2015), no. 5, 701–710.
[11] P. Roushini Leely Pushpam and M. Kamalam, Efficient weak Roman domination in Myscielski graphs, Int. J. Pure Eng. Math. 3 (2015), no. 2, 93–100.
[12] P. Roushini Leely Pushpam and T. Malini Mai, Weak Roman domination in graphs, Discuss. Math. Graph Theory 31 (2011), no. 1, 161–170.
Communications in Combinatorics and Optimization
Volume 8, Issue 3
September 2023
Pages 467-481

Files

Share

How to cite

Statistics