Strong equality of Roman and perfect Roman Domination in trees

Shao, Zehui; Kosari, Saeed; Rahbani, Hadi; Sharifzadeh, Mehdi; Sheikholeslami, Seyed Mahmoud

doi:10.1051/ro/2022005

Shao, Zehui ; Kosari, Saeed ; Rahbani, Hadi ; Sharifzadeh, Mehdi ; Sheikholeslami, Seyed Mahmoud

RAIRO. Operations Research, Tome 56 (2022) no. 1, pp. 381-394

Résumé

A Roman dominating function (RD-function) 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. An Roman dominating function f in a graph G is perfect Roman dominating function (PRD-function) if every vertex u with f(u) = 0 is adjacent to exactly one vertex v for which f(v) = 2. The (perfect) Roman domination number γ$$(G) ( $γ_{R}^{p} (G)$ ) is the minimum weight of an (perfect) Roman dominating function on G. We say that $γ_{R}^{p} (G)$ strongly equals γ$$(G), denoted by $γ_{R}^{p} (G) \equiv γ_{R} (G)$ , if every RD-function on G of minimum weight is a PRD-function. In this paper we show that for a given graph G, it is NP-hard to decide whether $γ_{R}^{p} (G) = γ_{R} (G)$ and also we provide a constructive characterization of trees T with $γ_{R}^{p} (T) \equiv γ_{R} (T)$ .

MR Zbl

DOI : 10.1051/ro/2022005

Classification : 05C69
Keywords: Perfect Roman dominating function, Roman dominating function

@article{RO_2022__56_1_381_0,
     author = {Shao, Zehui and Kosari, Saeed and Rahbani, Hadi and Sharifzadeh, Mehdi and Sheikholeslami, Seyed Mahmoud},
     title = {Strong equality of {Roman} and perfect {Roman} {Domination} in trees},
     journal = {RAIRO. Operations Research},
     pages = {381--394},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     number = {1},
     doi = {10.1051/ro/2022005},
     mrnumber = {4378550},
     zbl = {1486.05235},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2022005/}
}

TY  - JOUR
AU  - Shao, Zehui
AU  - Kosari, Saeed
AU  - Rahbani, Hadi
AU  - Sharifzadeh, Mehdi
AU  - Sheikholeslami, Seyed Mahmoud
TI  - Strong equality of Roman and perfect Roman Domination in trees
JO  - RAIRO. Operations Research
PY  - 2022
SP  - 381
EP  - 394
VL  - 56
IS  - 1
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2022005/
DO  - 10.1051/ro/2022005
LA  - en
ID  - RO_2022__56_1_381_0
ER  -

%0 Journal Article
%A Shao, Zehui
%A Kosari, Saeed
%A Rahbani, Hadi
%A Sharifzadeh, Mehdi
%A Sheikholeslami, Seyed Mahmoud
%T Strong equality of Roman and perfect Roman Domination in trees
%J RAIRO. Operations Research
%D 2022
%P 381-394
%V 56
%N 1
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2022005/
%R 10.1051/ro/2022005
%G en
%F RO_2022__56_1_381_0

Shao, Zehui; Kosari, Saeed; Rahbani, Hadi; Sharifzadeh, Mehdi; Sheikholeslami, Seyed Mahmoud. Strong equality of Roman and perfect Roman Domination in trees. RAIRO. Operations Research, Tome 56 (2022) no. 1, pp. 381-394. doi: 10.1051/ro/2022005

Bibliographie
Cité par

[1] J. Amjadi, M. Falahat, M. Chellali and S. M. Sheikholeslami, Unicyclic graphs with strong equality between the 2-rainbow domination and independent 2-rainbow domination numbers. Trans. Comb. 4 (2015) 1–11. | MR | Zbl

[2] J. Amjadi, M. Falahat, S. M. Sheikholeslami and N. Jafari Rad, Strong equality between the 2-rainbow domination and independent 2-rainbow domination numbers in trees. Bull. Malays. Math. Sci. Soc. 39 (2016) 205–218. | MR | Zbl | DOI

[3] J. D. Alvarado, S. Dantas and D. Rautenbach, Strong equality of Roman and weak Roman domination in trees. Discrete Appl. Math. 208 (2016) 19–26. | MR | Zbl | DOI

[4] A. Cabrera Martínez, A. Martínez Arias and M. Menendez Castillo, A characterization relating domination, semitotal domination and total Roman domination in trees. Commun. Comb. Optim. 6 (2021) 197–209. | MR | Zbl

[5] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami and L. Volkmann, Roman domination in graphs. In: Topics in Domination in Graphs, edited by T. W. Haynes, S. T. Hedetniemi and M. A. Henning. Springer, Berlin/Heidelberg (2020) 365–409. | MR | Zbl | DOI

[6] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami and L. Volkmann, Varieties of Roman domination II. AKCE Int. J Graphs Comb. 17 (2020) 966–984. | MR | Zbl | DOI

[7] M. Chellai, N. Jafari Rad, S. M. Sheikholeslami and L. Volkmann, A survey on Roman domination parameters in directed graphs. J. Combin. Math. Combin. Comput. 115 (2020) 141–171. | MR | Zbl

[8] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami and L. Volkmann, Varieties of Roman domination. In: Structures of Domination in Graphs, edited by T. W. Haynes, S. T. Hedetniemi and M. A. Henning. Springer, Berlin/Heidelberg (2021) 273–307. | MR | Zbl | DOI

[9] M. Chellali, N. Jafari Rad, S. M. Sheikholeslami and L. Volkmann, The Roman domatic problem in graphs and digraphs: a survey. Discuss. Math. Graph Theory (to appear). | MR | Zbl

[10] M. Chellali, S. M. Sheikholeslami and M. Soroudi, A characterization of perfect Roman trees. Discrete Appl. Math. 285 (2020) 501–508. | MR | Zbl | DOI

[11] E. J. Cockayne, P. M. Dreyer Jr, S. M. Hedetniemi and S. T. Hedetniemi, On Roman domination in graphs. Discrete Math. 278 (2004) 11–22. | MR | Zbl | DOI

[12] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979). | MR | Zbl

[13] T. W. Haynes, M. A. Henning and P. J. Slater, Strong equality of domination parameters in trees. Discrete Math. 260 (2003) 77–87. | MR | Zbl | DOI

[14] M. A. Henning and S. T. Hedetniemi, Defending the Roman empire – new strategy. Discrete Math. 266 (2003) 239–251. | MR | Zbl | DOI

[15] M. A. Henning, W. F. Klostermeyer and G. Macgillivray, Perfect Roman domination in trees. Discrete Appl. Math. 236 (2018) 235–245. | MR | Zbl | DOI

[16] N. Jafari Rad and C.-H. Liu, Trees with strong equality between the Roman domination number and the unique response Roman domination number. Australas. J. Combin. 54 (2012) 133–140. | MR | Zbl

[17] S. Nazari-Moghaddam and S. M. Sheikholeslami, On trees with equal Roman domination and outer-independent Roman domination number. Commun. Comb. Optim. 4 (2019) 185–199. | Zbl | MR

[18] Z. Shao, S. Kosari, M. Chellali, S. M. Sheikholeslami and M. Soroudi, On a relation between the perfect Roman domination and perfect domination numbers of a tree. Mathematics 8 (2020) 966. | DOI

[19] I. G. Yero and A. Cabrera Martínez, A characterization of trees with equal Roman {2}-domination and Roman domination numbers. Commun. Comb. Optim. 4 (2019) 95–107. | MR | Zbl

Cité par Sources :