Geodesic
On The Co-Roman Domination in Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 2, pp. 455-472.

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

Let G = (V, E) be a graph and let f : V (G) →0, 1, 2 be a function. A vertex v is said to be protected with respect to f, if f(v) gt; 0 or f(v) = 0 and v is adjacent to a vertex of positive weight. The function f is a co-Roman dominating function if (i) every vertex in V is protected, and (ii) each v ∈ V with positive weight has a neighbor u ∈ V with f(u) = 0 such that the function f_uv : V →0, 1, 2, defined by f_uv (u) = 1, f_uv(v) = f(v) − 1 and f_uv(x) = f(x) for x ∈ V \{ v, u }, has no unprotected vertex. The weight of f is ω(f) = Σ_ v ∈ V f(v). The co-Roman domination number of a graph G, denoted by γ_cr(G), is the minimum weight of a co-Roman dominating function on G. In this paper, we give a characterization of graphs of order n for which co-Roman domination number is 2n3 or n − 2, which settles two open problem in [S. Arumugam, K. Ebadi and M. Manrique, Co-Roman domination in graphs, Proc. Indian Acad. Sci. Math. Sci. 125 (2015) 1–10]. Furthermore, we present some sharp bounds on the co-Roman domination number.
Keywords: co-Roman dominating function, co-Roman domination number, Roman domination 
@article{DMGT_2019_39_2_a10,
     author = {Shao, Zehui and Sheikholeslami, Seyed Mahmoud and Soroudi, Marzieh and Volkmann, Lutz and Liu, Xinmiao},
     title = {On {The} {Co-Roman} {Domination} in {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {455--472},
     publisher = {mathdoc},
     volume = {39},
     number = {2},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a10/}
}
TY  - JOUR
AU  - Shao, Zehui
AU  - Sheikholeslami, Seyed Mahmoud
AU  - Soroudi, Marzieh
AU  - Volkmann, Lutz
AU  - Liu, Xinmiao
TI  - On The Co-Roman Domination in Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 455
EP  - 472
VL  - 39
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a10/
LA  - en
ID  - DMGT_2019_39_2_a10
ER  - 
%0 Journal Article
%A Shao, Zehui
%A Sheikholeslami, Seyed Mahmoud
%A Soroudi, Marzieh
%A Volkmann, Lutz
%A Liu, Xinmiao
%T On The Co-Roman Domination in Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 455-472
%V 39
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a10/
%G en
%F DMGT_2019_39_2_a10
Shao, Zehui; Sheikholeslami, Seyed Mahmoud; Soroudi, Marzieh; Volkmann, Lutz; Liu, Xinmiao. On The Co-Roman Domination in Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 2, pp. 455-472. http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a10/

[1] H. Abdollahzadeh Ahangar, M.A. Henning, V. Samodivkin and I.G. Yero, Total Roman domination in graphs, Appl. Anal. Discrete Math. 10 (2016) 501–517. doi:10.2298/AADM160802017A

[2] S. Arumugam, K. Ebadi and M. Manrique, Co-Roman dominaton in graphs, Proc. Indian Acad. Sci. Math. Sci. 125 (2015) 1–10. doi:10.1007/s12044-015-0209-8

[3] R.A. Beeler, T.W. Haynes and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016) 23–29. doi:10.1016/j.dam.2016.03.017

[4] E.W. Chambers, B. Kinnersley, N. Prince and D.B. West, Extremal problems for Roman domination, SIAM J. Discrete Math. 23 (2009) 1575–1586. doi:10.1137/070699688

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

[6] E.J. Cockayne, P.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

[7] O. Favaron, H. Karami, R. Khoeilar and S.M. Sheikholeslami, On the Roman domination number of a graph, Discrete Math. 309 (2009) 3447–3451. doi:10.1016/j.disc.2008.09.043

[8] J. Fink, M. Jacobson, L. Kinch and J. Roberts, On graphs having domination number half their order, Period. Math. Hungar. 16 (1985) 287–293. doi:10.1007/BF01848079

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

[10] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker Inc., New York, 1998).

[11] M.A. Henning and S.T. Hedetniemi, Defending the Roman Empire—A new strategy, Discrete Math. 266 (2003) 239–251. doi:10.1016/S0012-365X(02)00811-7

[12] C. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982) 23–32. doi:10.1002/jgt.3190060104

[13] 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

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

[15] Z. Zhang, Z. Shao and X. Xu, On the Roman domination numbers of generalized Petersen graphs, J. Combin. Math. Combin. Comput. 89 (2014) 311–320.