Geodesic
Bounds on the Locating Roman Domination Number in Trees
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 49-62.

Voir la notice de l'article provenant de la source Library of Science

A Roman dominating function (or just 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 RDF f is the value f(V (G)) = Σ_ u ∈ V (G) f(u). An RDF f can be represented as f = (V_0, V_1, V_2), where V_i = { v ∈ V : f(v) = i } for i = 0, 1, 2. An RDF f = (V_0, V_1, V_2) is called a locating Roman dominating function (or just LRDF) if N(u) ∩ V_2 N(v) ∩ V_2 for any pair u, v of distinct vertices of V_0. The locating Roman domination number γ_R^L (G) is the minimum weight of an LRDF of G. In this paper, we study the locating Roman domination number in trees. We obtain lower and upper bounds for the locating Roman domination number of a tree in terms of its order and the number of leaves and support vertices, and characterize trees achieving equality for the bounds.
Keywords: Roman domination number, locating domination number, locating Roman domination number, tree 
@article{DMGT_2018_38_1_a3,
     author = {Jafari Rad, Nader and Rahbani, Hadi},
     title = {Bounds on the {Locating} {Roman} {Domination} {Number} in {Trees}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {49--62},
     publisher = {mathdoc},
     volume = {38},
     number = {1},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a3/}
}
TY  - JOUR
AU  - Jafari Rad, Nader
AU  - Rahbani, Hadi
TI  - Bounds on the Locating Roman Domination Number in Trees
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 49
EP  - 62
VL  - 38
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a3/
LA  - en
ID  - DMGT_2018_38_1_a3
ER  - 
%0 Journal Article
%A Jafari Rad, Nader
%A Rahbani, Hadi
%T Bounds on the Locating Roman Domination Number in Trees
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 49-62
%V 38
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a3/
%G en
%F DMGT_2018_38_1_a3
Jafari Rad, Nader; Rahbani, Hadi. Bounds on the Locating Roman Domination Number in Trees. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 49-62. http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a3/

[1] M. Adabi, E. Ebrahimi Targhi, N. Jafari Rad and M. Saied Moradi, Properties of independent Roman domination in graphs, Australas. J. Combin. 52 (2012) 11–18.

[2] H.A. Ahangar, M.A. Henning, V. Samodivkin and I.G. Yero, Total Roman domination in graphs, manuscript (2014).

[3] H.A. Ahangar, M.A. Henning, C. Löwenstein, Y. Zhao and V. Samodivkin, Signed Roman domination in graphs, J. Comb. Optim. 27 (2014) 241–255. doi:10.1007/s10878-012-9500-0

[4] M. Blidia, M. Chellali, F. Maffray, J. Moncel and A. Semri, Locating-domination and identifying codes in trees, Australas. J. Combin. 39 (2007) 219–232.

[5] M. Blidia, O. Favaron and R. Lounes, Locating-domination, 2- domination and independence in trees, Australas. J. Combin. 42 (2008) 309–319.

[6] M. Chellali, On locating and differentiating-total domination in trees, Discuss. Math. Graph Theory 28 (2008) 383–392. doi:10.7151/dmgt.1414

[7] M. Chellali, T.W. Haynes, S.T. Hedetniemi and A.A. McRae, Roman 2- domination, Discrete Appl. Math. 204 (2016) 22–28. doi:10.1016/j.dam.2015.11.013

[8] M. Chellali and N. Jafari Rad, Locating-total domination critical graphs, Australas. J. Combin. 45 (2009) 227–234.

[9] X.G. Chen and M.Y. Sohn, Bounds on the locating-total domination number of a tree, Discrete Appl. Math. 159 (2011) 769–773. doi:10.1016/j.dam.2010.12.025

[10] E.J. Cockayne, Paul A. Dreyer Jr., S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11–22. doi:10.1016/j.disc.2003.06.004

[11] F. Foucaud, M.A. Henning, C. Löwenstein and T. Sass, Locating-dominating sets in twin-free graphs, Discrete Appl. Math. 200 (2016) 52–58. doi:10.1016/j.dam.2015.06.038

[12] T.W. Haynes, M.A. Henning and J. Howard, Locating and total dominating sets in trees, Discrete Appl. Math. 154 (2006) 1293–1300. doi:10.1016/j.dam.2006.01.002

[13] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).

[14] M.A. Henning and N. Jafari Rad, Locating-total domination in graphs, Discrete Appl. Math. 160 (2012) 1986–1993. doi:10.1016/j.dam.2012.04.004

[15] M.A. Henning and C. Löwenstein, Locating-total domination in claw-free cubic graphs, Discrete Math. 312 (2012) 3107–3116. doi:10.1016/j.disc.2012.06.024

[16] N. Jafari Rad, H. Rahbani and L. Volkmann, Locating Roman domination in graphs, manuscript (2015).

[17] K. Kammerling and L. Volkmann, Roman k-domination in graphs, J. Korean Math. Soc. 46 (2009) 1309–1318. doi:10.4134/JKMS.2009.46.6.1309

[18] J.L. Sewell and P.J. Slater, A sharp lower bound for locating-dominating sets in trees, Australas. J. Combin. 60 (2014) 136–149.

[19] C.S. ReVelle and K.E. Rosing, Defendens imperium Romanum: a classical problem in military strategy, Amer Math. Monthly 107 (2000) 585–594. doi:10.2307/2589113

[20] P. Roushini Leely Pushpam and T.N.M. Nalini Mai, Edge Roman domination in graphs, J. Combin. Math. Combin. Comput. 69 (2009) 175–182.

[21] P.J. Slater, Dominating and location in acyclic graphs, Networks 17 (1987) 55–64. doi:10.1002/net.3230170105

[22] P.J. Slater, Dominating and reference sets in graphs, J. Math. Phys. Sci. 22 (1988) 445–455.

[23] S.J. Seo and P.J. Slater, Open neighborhood locating-dominating sets, Australas. J. Combin. 46 (2010) 109–120.

[24] I. Stewart, Defend the Roman Empire !, Sci. Amer. 281 (1999) 136–139. doi:10.1038/scientificamerican1299-136