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)→{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)→{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′:V(G)→{0,1,2} defined by f′(u)=1, f′(v)=f(v)−1 and f′(w)=f(w) if w∈V−{u,v}, has no undefended vertex. A graph G is said to be Roman domination stable upon edge addition, or just γR-EA-stable, if γR(G+e)=γR(G) for any edge e∉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 γr-EA-stable, if γr(G+e)=γr(G) for any edge e∉E(G). In this paper, we study γr-EA-stable graphs, obtain bounds for  γr-EA-stable graphs and  characterize γ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