A characterization of locating Roman domination edge critical graphs

Document Type : Original paper

Authors

1 Department of Mathematics, Babol Noshirvani University of Technology, Shariati Ave., Babol, I.R. Iran

2 Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, I.R. Iran

Abstract

A Roman dominating function (or just \textit{RDF}) on a graph G=(V,E) is a function f:V⟶{0,1,2} satisfying the condition that every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. The weight of an \textit{RDF} f is the value f(V)=∑u∈Vf(u). An \textit{RDF} f can be represented as f=(V0,V1,V2), where Vi={v∈V:f(v)=i} for i=0,1,2. An \textit{RDF} f=(V0,V1,V2) is called a locating Roman dominating function (or just \textit{L\textit{RDF}}) if N(u)∩V2≠N(v)∩V2 for any pair u,v of distinct vertices of V0. The locating-Roman domination number γRL(G) is the minimum weight of an \textit{L\textit{RDF}} of G. A graph G is said to be a locating Roman domination edge  critical graph, or just γRL-edge critical graph, if γRL(G−e)>γRL(G) for all e∈E. The purpose of this paper is to characterize the class of γRL-edge critical graphs.

Keywords

Main Subjects

References

[1] R.C. Brigham, P.Z. Chinn, and R.D. Dutton, Vertex domination-critical graphs, Networks 18 (1988), no. 3, 173–179. https://doi.org/10.1002/net.3230180304
[2] M. Chellali and N. Jafari Rad, Locating-total domination critical graphs., Australas. J. Comb. 45 (2009), 227–234.
[3] R.D. Dutton and R.C. Brigham, On global domination critical graphs, Discrete Math. 309 (2009), no. 19, 5894–5897. https://doi.org/10.1016/j.disc.2008.06.005
[4] W. Goddard, T.W. Haynes, M.A. Henning, and L.C. Van der Merwe, The diameter of total domination vertex critical graphs, Discrete Math. 286 (2004), no. 3, 255–261. https://doi.org/10.1016/j.disc.2004.05.010
[5] P.J.P. Grobler and C.M. Mynhardt, Secure domination critical graphs, Discrete Math. 309 (2009), no. 19, 5820–5827. https://doi.org/10.1016/j.disc.2008.05.050
[6] A. Hansberg, N. Jafari Rad, and L. Volkmann, Characterization of Roman domination critical unicyclic graphs, Util. Math. 86 (2011), 129–146. 
[7] A. Hansberg, N. Jafari Rad, and L. Volkmann, Vertex and edge critical Roman domination in graphs, Util. Math. 92
(2013), 73–88.
[8] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc. New York, 1998.
[9] N. Jafari Rad, Critical concept for 2-rainbow domination in graphs, Australas. J. Comb. 51 (2011), 49–60.
[10] N. Jafari Rad, Roman domination critical graphs upon edge subdivision, J. Combin. Math. Combin. Comput. 93 (2015), 227–245.
[11] N. Jafari Rad and H. Rahbani, Bounds on the locating Roman domination number in trees, Discuss. Math. Graph Theory 38 (2018), no. 1, 49–62.  http://doi.org/10.7151/dmgt.1989
[12] N. Jafari Rad, H. Rahbani, and L. Volkmann, Locating Roman domination in graphs, Util. Math. 110 (2019), 203–222.
[13] P.J. Slater, Domination and location in acyclic graphs, Networks 17 (1987), no. 1, 55–64. https://doi.org/10.1002/net.3230170105
[14] P.J. Slater, Dominating and reference sets in graphs, J. Math. Phys. Sci 22 (1988), 445–455.
[15] I. Stewart, Defend the Roman empire!, Scientific American 281 (1999), no. 6, 136–138.
Communications in Combinatorics and Optimization
Volume 10, Issue 3
September 2025
Pages 531-537

Files

Share

How to cite

Statistics