Geodesic
Total Roman {2}-Dominating Functions in Graphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 937-958 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

A Roman 2-dominating function (R2F) is a function f : V → 0, 1, 2 with the property that for every vertex v ∈ V with f(v) = 0 there is a neighbor u of v with f(u) = 2, or there are two neighbors x, y of v with f(x) = f(y) = 1. A total Roman 2-dominating function (TR2DF) is an R2F f such that the set of vertices with f(v) gt; 0 induce a subgraph with no isolated vertices. The weight of a TR2DF is the sum of its function values over all vertices, and the minimum weight of a TR2DF of G is the total Roman 2-domination number γtR2(G). In this paper, we initiate the study of total Roman 2-dominating functions, where properties are established. Moreover, we present various bounds on the total Roman 2-domination number. We also show that the decision problem associated with γtR2(G) is possible to compute this parameter in linear time for bounded clique-width graphs (including trees).
Keywords: Roman domination, Roman {2}-domination, total Roman {2}-domination 
@article{DMGT_2022_42_3_a15,
     author = {Ahangar, H. Abdollahzadeh and Chellali, M. and Sheikholeslami, S.M. and Valenzuela-Tripodoro, J.C.},
     title = {Total {Roman} {{2}-Dominating} {Functions} in {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {937--958},
     year = {2022},
     volume = {42},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a15/}
}
TY  - JOUR
AU  - Ahangar, H. Abdollahzadeh
AU  - Chellali, M.
AU  - Sheikholeslami, S.M.
AU  - Valenzuela-Tripodoro, J.C.
TI  - Total Roman {2}-Dominating Functions in Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 937
EP  - 958
VL  - 42
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a15/
LA  - en
ID  - DMGT_2022_42_3_a15
ER  - 
%0 Journal Article
%A Ahangar, H. Abdollahzadeh
%A Chellali, M.
%A Sheikholeslami, S.M.
%A Valenzuela-Tripodoro, J.C.
%T Total Roman {2}-Dominating Functions in Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 937-958
%V 42
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a15/
%G en
%F DMGT_2022_42_3_a15
Ahangar, H. Abdollahzadeh; Chellali, M.; Sheikholeslami, S.M.; Valenzuela-Tripodoro, J.C. Total Roman {2}-Dominating Functions in Graphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 937-958. http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a15/

[1] B. Bollobás and E.J. Cockayne, Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory 3 (1979) 241–249. https://doi.org/10.1002/jgt.3190030306

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

[3] H. Chen and C. Lu, A note on Roman 2 -domination problem in graphs . arXiv:1804-09338

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

[5] B. Courcelle, J.A. Makowsky and U. Rotics, Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst. 33 (2000) 125–150. https://doi.org/10.1007/s002249910009

[6] F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000) 201–213.

[7] W. Klostermeyer and G. MacGillivray, Roman, Italian, and 2 -domination, J. Combin. Math. Combin. Comput. 108 (2019) 125–146.

[8] M. Liedloff, T. Kloks, J. Liu and S.L. Peng, Effcient algorithms for Roman domination on some classes of graphs, Discrete Appl. Math. 156 (2008) 3400–3415. https://doi.org/10.1016/j.dam.2008.01.011

[9] C.S. ReVelle, Can you protect the Roman Empire ? Johns Hopkins Magazine 49 (1997) 40.

[10] C.S. ReVelle and K.E. Rosing, Defendens Imperium Romanum: A classical problem in military strategy, Amer. Math. Monthly 107 (2000) 585–594. https://doi.org/10.1080/00029890.2000.12005243

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