{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T00:57:51Z","timestamp":1778633871519,"version":"3.51.4"},"reference-count":13,"publisher":"EDP Sciences","issue":"4","license":[{"start":{"date-parts":[[2023,7,24]],"date-time":"2023-07-24T00:00:00Z","timestamp":1690156800000},"content-version":"vor","delay-in-days":23,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2023,4,4]]},"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:p>The study of a variant of Roman domination was initiated by Chellali <jats:italic>et al.<\/jats:italic> [<jats:italic>Discrete Appl. Math.<\/jats:italic> <jats:bold>204<\/jats:bold> (2016) 22\u201328]. Given a graph <jats:italic>G<\/jats:italic> with vertex set <jats:italic>V<\/jats:italic>, a Roman {2}-dominating function <jats:italic>f<\/jats:italic>\u00a0:\u00a0<jats:italic>V<\/jats:italic>\u00a0\u2192\u00a0{0,\u00a01,\u00a02} has the property that for every vertex <jats:italic>v<\/jats:italic> \u2208 <jats:italic>V<\/jats:italic> with <jats:italic>f<\/jats:italic>(<jats:italic>v<\/jats:italic>) = 0, either there exists a vertex <jats:italic>u<\/jats:italic> adjacent to <jats:italic>v<\/jats:italic> with <jats:italic>f<\/jats:italic>(<jats:italic>u<\/jats:italic>) = 2, or at least two vertices <jats:italic>x<\/jats:italic>, <jats:italic>y<\/jats:italic> adjacent to <jats:italic>v<\/jats:italic> with <jats:italic>f<\/jats:italic>(<jats:italic>x<\/jats:italic>) = <jats:italic>f<\/jats:italic>(<jats:italic>y<\/jats:italic>) = 1. The weight of a Roman {2}-dominating function is the value <jats:italic>f<\/jats:italic>(<jats:italic>V<\/jats:italic>) = \u2211<jats:sub><jats:italic>v<\/jats:italic>\u2208V<\/jats:sub>\u00a0<jats:italic>f<\/jats:italic>(<jats:italic>v<\/jats:italic>). The minimum weight of a Roman {2}-dominating function is called the Roman {2}-domination number and is denoted by <jats:italic>\u03b3<\/jats:italic><jats:sub>{R2}<\/jats:sub>(<jats:italic>G<\/jats:italic>). In this work we find several NP-complete instances of the Roman {2}-domination problem: chordal graphs, bipartite planar graphs, chordal bipartite graphs, bipartite with maximum degree 3 graphs, among others. A result by Chellali <jats:italic>et al.<\/jats:italic> [<jats:italic>Discrete Appl. Math.<\/jats:italic> <jats:bold>204<\/jats:bold> (2016) 22\u201328] shows that <jats:italic>\u03b3<\/jats:italic><jats:sub>{R2}<\/jats:sub>(<jats:italic>G<\/jats:italic>) and the 2-rainbow domination number of G coincide when <jats:italic>G<\/jats:italic> is a tree, and thus, the linear time algorithm for <jats:italic>k<\/jats:italic>-rainbow domination due to Bre\u0161ar <jats:italic>et al.<\/jats:italic> [<jats:italic>Taiwan J. Math.<\/jats:italic> <jats:bold>12<\/jats:bold> (2008) 213\u2013225] can be followed to compute <jats:italic>\u03b3<\/jats:italic><jats:sub>{R2}<\/jats:sub>(<jats:italic>G<\/jats:italic>). In this work we develop an efficient algorithm that is independent of <jats:italic>k<\/jats:italic>-rainbow domination and computes the Roman {2}-domination number on a subclass of trees called caterpillars.<\/jats:p>","DOI":"10.1051\/ro\/2023049","type":"journal-article","created":{"date-parts":[[2023,4,7]],"date-time":"2023-04-07T08:07:25Z","timestamp":1680854845000},"page":"1905-1912","source":"Crossref","is-referenced-by-count":7,"title":["New complexity results on Roman {2}-domination"],"prefix":"10.1051","volume":"57","author":[{"given":"Lara","family":"Fern\u00e1ndez","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valeria","family":"Leoni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2023,7,24]]},"reference":[{"key":"R1","unstructured":"Abdollahzadeh Ahangar H., Bahremandpour A., Sheikholeslami S.M., Soner N.D., Tahmasbzadehbaee Z. and Volkmann L., Maximal Roman domination numbers in graphs. Util. Math. 103 (2017)."},{"key":"R2","first-page":"1444","volume":"40","author":"Abdollahzadeh Ahangar","year":"2015","journal-title":"Bull. Malays. Math. Sci. Soc."},{"key":"R3","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.dam.2016.03.017","volume":"211","author":"Beeler","year":"2016","journal-title":"Discrete Appl. Math."},{"key":"R4","doi-asserted-by":"crossref","first-page":"213","DOI":"10.11650\/twjm\/1500602498","volume":"12","author":"Bre\u0161ar","year":"2008","journal-title":"Taiwan J. Math."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Bondy J.A. and Murty U.S.R., Graph Theory, Springer Publishing Company Incorporated (2008).","DOI":"10.1007\/978-1-84628-970-5"},{"key":"R6","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1016\/j.dam.2009.08.010","volume":"158","author":"Chang","year":"2010","journal-title":"Discrete Appl. Math."},{"key":"R7","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.dam.2015.11.013","volume":"204","author":"Chellali","year":"2016","journal-title":"Discrete Appl. Math."},{"key":"R8","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.disc.2003.06.004","volume":"278","author":"Cockaynea","year":"2004","journal-title":"Discrete Math."},{"key":"R9","first-page":"239","volume":"266","author":"Henning","year":"2003","journal-title":"Discrete Appl. Math."},{"key":"R10","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1016\/j.dam.2016.09.035","volume":"217","author":"Henning","year":"2017","journal-title":"Discrete Appl. Math."},{"key":"R11","first-page":"125","volume":"108","author":"Klostermeyer","year":"2019","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"R12","doi-asserted-by":"crossref","first-page":"1081","DOI":"10.1016\/j.akcej.2020.01.005","volume":"17","author":"Padamutham","year":"2020","journal-title":"AKCE Int. J Graphs Comb."},{"key":"R13","doi-asserted-by":"crossref","first-page":"791","DOI":"10.1007\/s40995-020-00875-7","volume":"44","author":"Poureidi","year":"2020","journal-title":"Iran. J. Sci. Technol. Trans. Sci."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023049\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,24]],"date-time":"2023-07-24T08:16:55Z","timestamp":1690186615000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023049"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7]]},"references-count":13,"journal-issue":{"issue":"4"},"alternative-id":["ro220776"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2023049","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"2804-7303","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7]]}}}