A characterization of locating Roman domination edge critical graphs

Articles in Press

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 \longrightarrow \{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)=\sum_{u \in {V}}f(u)$. An \textit{RDF} $f$ can be represented as $f=(V_0,V_1,V_2)$, where $V_i=\{v\in V:f(v)=i\}$ for $i=0,1,2$. An \textit{RDF} $f=(V_0,V_1,V_2)$ is called a locating Roman dominating function (or just \textit{L\textit{RDF}}) if $N(u)\cap V_2\neq N(v)\cap V_2$ for any pair $u,v$ of distinct vertices of $V_0$. The locating-Roman domination number $\gamma_R^L(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 $\gamma_R^L$-edge critical graph, if $\gamma_R^L(G-e)>\gamma_R^L(G)$ for all $e\in E$. The purpose of this paper is to characterize the class of $\gamma_R^L$-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

Articles in Press, Accepted Manuscript
Available Online from 26 December 2023

Files

Share

How to cite

Statistics