{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T18:10:41Z","timestamp":1758823841686,"version":"3.37.3"},"reference-count":19,"publisher":"EDP Sciences","issue":"1","license":[{"start":{"date-parts":[[2022,2,10]],"date-time":"2022-02-10T00:00:00Z","timestamp":1644451200000},"content-version":"vor","delay-in-days":40,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2022,1,9]]},"published-print":{"date-parts":[[2022,1]]},"abstract":"<jats:p>A Roman dominating function (RD-function) on a graph <jats:italic>G<\/jats:italic> = (<jats:italic>V<\/jats:italic>,\u00a0<jats:italic>E<\/jats:italic>) is a function <jats:italic>f<\/jats:italic> : <jats:italic>V<\/jats:italic> \u2192 {0,\u00a01,\u00a02} satisfying the condition that every vertex <jats:italic>u<\/jats:italic> for which <jats:italic>f<\/jats:italic>(<jats:italic>u<\/jats:italic>) = 0 is adjacent to at least one vertex <jats:italic>v<\/jats:italic> for which <jats:italic>f<\/jats:italic>(<jats:italic>v<\/jats:italic>) = 2. An Roman dominating function <jats:italic>f<\/jats:italic> in a graph <jats:italic>G<\/jats:italic> is perfect Roman dominating function (PRD-function) if every vertex <jats:italic>u<\/jats:italic> with <jats:italic>f<\/jats:italic>(<jats:italic>u<\/jats:italic>) = 0 is adjacent to exactly one vertex <jats:italic>v<\/jats:italic> for which <jats:italic>f<\/jats:italic>(<jats:italic>v<\/jats:italic>) = 2. The (perfect) Roman domination number <jats:italic>\u03b3<\/jats:italic><jats:sub><jats:italic>R<\/jats:italic><\/jats:sub>(<jats:italic>G<\/jats:italic>) (<jats:italic>\u03b3<\/jats:italic><jats:sup>p<\/jats:sup><jats:italic><jats:sub>R<\/jats:sub><\/jats:italic>(<jats:italic>G<\/jats:italic>)) is the minimum weight of an (perfect) Roman dominating function on <jats:italic>G<\/jats:italic>. We say that <jats:italic>\u03b3<\/jats:italic><jats:sup>p<\/jats:sup><jats:italic><jats:sub>R<\/jats:sub><\/jats:italic>(<jats:italic>G<\/jats:italic>) strongly equals <jats:italic>\u03b3<\/jats:italic><jats:sub><jats:italic>R<\/jats:italic><\/jats:sub>(<jats:italic>G<\/jats:italic>), denoted by <jats:italic>\u03b3<\/jats:italic><jats:sup>p<\/jats:sup><jats:italic><jats:sub>R<\/jats:sub><\/jats:italic>(<jats:italic>G<\/jats:italic>) \u2261 <jats:italic>\u03b3R<\/jats:italic>(<jats:italic>G<\/jats:italic>), if every RD-function on <jats:italic>G<\/jats:italic> of minimum weight is a PRD-function. In this paper we show that for a given graph <jats:italic>G<\/jats:italic>, it is NP-hard to decide whether <jats:italic>\u03b3<\/jats:italic><jats:sup>p<\/jats:sup><jats:italic>R<\/jats:italic>(<jats:italic>G<\/jats:italic>) = <jats:italic>\u03b3R<\/jats:italic>(<jats:italic>G<\/jats:italic>) and also we provide a constructive characterization of trees <jats:italic>T<\/jats:italic> with <jats:italic>\u03b3<\/jats:italic><jats:sup>p<\/jats:sup><jats:italic>R<\/jats:italic>(<jats:italic>T<\/jats:italic>) \u2261 <jats:italic>\u03b3R<\/jats:italic>(<jats:italic>T<\/jats:italic>).<\/jats:p>","DOI":"10.1051\/ro\/2022005","type":"journal-article","created":{"date-parts":[[2022,1,11]],"date-time":"2022-01-11T08:56:43Z","timestamp":1641891403000},"page":"381-394","source":"Crossref","is-referenced-by-count":5,"title":["Strong equality of Roman and perfect Roman Domination in trees"],"prefix":"10.1051","volume":"56","author":[{"given":"Zehui","family":"Shao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saeed","family":"Kosari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hadi","family":"Rahbani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9046-9771","authenticated-orcid":false,"given":"Mehdi","family":"Sharifzadeh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2298-4744","authenticated-orcid":false,"given":"Seyed Mahmoud","family":"Sheikholeslami","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2022,2,10]]},"reference":[{"key":"R1","first-page":"1","volume":"4","author":"Amjadi","year":"2015","journal-title":"Trans. Comb."},{"key":"R2","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/s40840-015-0284-0","volume":"39","author":"Amjadi","year":"2016","journal-title":"Bull. Malays. Math. Sci. Soc."},{"key":"R3","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.dam.2016.03.004","volume":"208","author":"Alvarado","year":"2016","journal-title":"Discrete Appl. Math."},{"key":"R4","first-page":"197","volume":"6","author":"Cabrera Mart\u00ednez","year":"2021","journal-title":"Commun. Comb. Optim."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Chellali M., Jafari Rad N., Sheikholeslami S.M. and Volkmann L., Roman domination in graphs. In: Topics in Domination in Graphs, edited by Haynes T.W., Hedetniemi S.T. and Henning M.A.. Springer, Berlin\/Heidelberg (2020) 365\u2013409.","DOI":"10.1007\/978-3-030-51117-3_11"},{"key":"R6","doi-asserted-by":"crossref","first-page":"966","DOI":"10.1016\/j.akcej.2019.12.001","volume":"17","author":"Chellali","year":"2020","journal-title":"AKCE Int. J Graphs Comb."},{"key":"R7","first-page":"141","volume":"115","author":"Chellai","year":"2020","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Chellali M., Jafari Rad N., Sheikholeslami S.M. and Volkmann L., Varieties of Roman domination. In: Structures of Domination in Graphs, edited by Haynes T.W., Hedetniemi S.T. and Henning M.A.. Springer, Berlin\/Heidelberg (2021) 273\u2013307.","DOI":"10.1007\/978-3-030-58892-2_10"},{"key":"R9","unstructured":"Chellai M., Jafari Rad N., Sheikholeslami S.M. and Volkmann L., The Roman domatic problem in graphs and digraphs: a survey. Discuss. Math. Graph Theory (to appear)."},{"key":"R10","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1016\/j.dam.2020.06.014","volume":"285","author":"Chellali","year":"2020","journal-title":"Discrete Appl. Math."},{"key":"R11","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.disc.2003.06.004","volume":"278","author":"Cockayne","year":"2004","journal-title":"Discrete Math."},{"key":"R12","unstructured":"Garey M.R. and Johnson D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)."},{"key":"R13","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0012-365X(02)00451-X","volume":"260","author":"Haynes","year":"2003","journal-title":"Discrete Math."},{"key":"R14","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/S0012-365X(02)00811-7","volume":"266","author":"Henning","year":"2003","journal-title":"Discrete Math."},{"key":"R15","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/j.dam.2017.10.027","volume":"236","author":"Henning","year":"2018","journal-title":"Discrete Appl. Math."},{"key":"R16","first-page":"133","volume":"54","author":"Jafari Rad","year":"2012","journal-title":"Australas. J. Combin."},{"key":"R17","first-page":"185","volume":"4","author":"Nazari-Moghaddam","year":"2019","journal-title":"Commun. Comb. Optim."},{"key":"R18","doi-asserted-by":"crossref","first-page":"966","DOI":"10.3390\/math8060966","volume":"8","author":"Shao","year":"2020","journal-title":"Mathematics"},{"key":"R19","first-page":"95","volume":"4","author":"Yero","year":"2019","journal-title":"Commun. Comb. Optim."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2022005\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,10]],"date-time":"2022-02-10T09:03:43Z","timestamp":1644483823000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2022005"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1]]},"references-count":19,"journal-issue":{"issue":"1"},"alternative-id":["ro200336"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2022005","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2022,1]]}}}