{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:47:40Z","timestamp":1770994060966,"version":"3.50.1"},"reference-count":29,"publisher":"EDP Sciences","issue":"4","license":[{"start":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T00:00:00Z","timestamp":1719878400000},"content-version":"vor","delay-in-days":1,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62172116"],"award-info":[{"award-number":["62172116"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2024,2,7]]},"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:p>For a simple undirected connected graph <jats:italic>G<\/jats:italic> = (<jats:italic>V, E<\/jats:italic>), a maximal Roman dominating function (MRDF) of <jats:italic>G<\/jats:italic> is a function <jats:italic>f<\/jats:italic> : <jats:italic>V<\/jats:italic> (<jats:italic>G<\/jats:italic>) \u2192 {0, 1, 2} with the following properties: (<jats:italic>i<\/jats:italic>) For every vertex <jats:italic>v<\/jats:italic> \u2208 {<jats:italic>v<\/jats:italic> \u2208 <jats:italic>V<\/jats:italic>|<jats:italic>f<\/jats:italic>(<jats:italic>v<\/jats:italic>) = 0}, there exists a vertex <jats:italic>u<\/jats:italic> \u2208 <jats:italic>N<\/jats:italic>(<jats:italic>v<\/jats:italic>) such that <jats:italic>f<\/jats:italic>(<jats:italic>u<\/jats:italic>) = 2. (<jats:italic>ii<\/jats:italic>) The set {<jats:italic>v<\/jats:italic> \u2208 <jats:italic>V|f<\/jats:italic>(<jats:italic>v<\/jats:italic>) = 0} is not a dominating set of <jats:italic>G<\/jats:italic>; In other words, there exists a vertex <jats:italic>v<\/jats:italic> \u2208 {<jats:italic>v<\/jats:italic> \u2208 <jats:italic>V<\/jats:italic>|<jats:italic>f<\/jats:italic>(<jats:italic>v<\/jats:italic>) \u2260 0} such that <jats:italic>N<\/jats:italic>(<jats:italic>v<\/jats:italic>) \u2229 {<jats:italic>u<\/jats:italic> \u2208 <jats:italic>V<\/jats:italic>|<jats:italic>f<\/jats:italic>(<jats:italic>u<\/jats:italic>) = 0} <jats:italic>\u2205<\/jats:italic>. The weight of an MRDF of <jats:italic>G<\/jats:italic> is the sum of its function values over all vertices, denoted as <jats:italic>f<\/jats:italic>(<jats:italic>G<\/jats:italic>) = \u2211<jats:sub><jats:italic>v<\/jats:italic>\u2208<jats:italic>V<\/jats:italic> (<jats:italic>G<\/jats:italic>)<\/jats:sub> <jats:italic>f<\/jats:italic>(<jats:italic>v<\/jats:italic>), and the maximal Roman domination number of <jats:italic>G<\/jats:italic>, denoted by <jats:italic>\u03b3<\/jats:italic><jats:italic><jats:sub>mR<\/jats:sub><\/jats:italic>(<jats:italic>G<\/jats:italic>), is the minimum weight of an MRDF of <jats:italic>G<\/jats:italic>. In this paper, we establish some bounds of the maximal Roman domination number of graphs. Additionally, we develop an integer linear programming formulation to compute the maximal Roman domination number of any graph. Furthermore, we prove that maximal Roman domination problem (MRD) is NP-complete even restricted to star convex bipartite graphs and chordal bipartite graphs. Lastly, we show the maximal Roman domination number of threshold graphs, trees, and block graphs can be computed in linear time.<\/jats:p>","DOI":"10.1051\/ro\/2024038","type":"journal-article","created":{"date-parts":[[2024,2,13]],"date-time":"2024-02-13T14:10:57Z","timestamp":1707833457000},"page":"2709-2731","source":"Crossref","is-referenced-by-count":1,"title":["On maximal Roman domination in graphs: complexity and algorithms"],"prefix":"10.1051","volume":"58","author":[{"given":"Zehui","family":"Shao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yonghao","family":"Song","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qiyun","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhixing","family":"Duan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3316-877X","authenticated-orcid":false,"given":"Huiqin","family":"Jiang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2024,7,2]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Bondy J.A. and Murty U.S.R., Graph Theory with Applications. Vol. 290. Macmillan London (1976).","DOI":"10.1007\/978-1-349-03521-2"},{"key":"R2","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1038\/scientificamerican1299-136","volume":"281","author":"Stewart","year":"1999","journal-title":"Sci. Am."},{"key":"R3","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1080\/00029890.2000.12005243","volume":"107","author":"ReVelle","year":"2000","journal-title":"Am. Math. Monthly"},{"key":"R4","first-page":"157","volume":"5","author":"Amjadi","year":"2020","journal-title":"Commun. Comb. Optim."},{"key":"R5","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":"R6","doi-asserted-by":"crossref","first-page":"2547","DOI":"10.1080\/00207160.2017.1301437","volume":"94","author":"Ahangar","year":"2017","journal-title":"Int. J. Comput. Math."},{"key":"R7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2019.08.017","volume":"796","author":"Banerjee","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"R8","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1016\/j.dam.2015.07.014","volume":"200","author":"Pushpam","year":"2016","journal-title":"Discrete Appl. Math."},{"key":"R9","first-page":"245","volume":"103","author":"Ahangar","year":"2017","journal-title":"Util. Math."},{"key":"R10","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/978-3-030-58892-2_10","volume":"66","author":"Chellali","year":"2021","journal-title":"Struct. Domination Graphs"},{"key":"R11","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":"R12","doi-asserted-by":"crossref","first-page":"1093","DOI":"10.1080\/00207160.2015.1052804","volume":"93","author":"Abdollahzadeh Ahangar","year":"2016","journal-title":"Int. J. Comput. Math."},{"key":"R13","first-page":"207","volume":"144","author":"Ahangar","year":"2019","journal-title":"ARS Comb."},{"key":"R14","first-page":"197","volume":"6","author":"Kamalipashakolaee","year":"2020","journal-title":"J. New Res. Math."},{"key":"R15","first-page":"11","volume":"33","author":"Kulli","year":"1997","journal-title":"Graph Theory Notes New York"},{"key":"R16","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/j.akcej.2016.06.009","volume":"13","author":"Ahangar","year":"2016","journal-title":"AKCE Int. J. Graphs Comb."},{"key":"R17","first-page":"126662","volume":"414","author":"Ahangar","year":"2022","journal-title":"Appl. Math. Comput."},{"key":"R18","doi-asserted-by":"crossref","first-page":"63345","DOI":"10.1109\/ACCESS.2018.2876460","volume":"6","author":"Shao","year":"2018","journal-title":"IEEE Access"},{"key":"R19","unstructured":"Alon N. and Spencer J.H., The Probabilistic Method. John Wiley & Sons (2016)."},{"key":"R20","first-page":"19","volume":"67","author":"Cockayne","year":"2005","journal-title":"Util. Math."},{"key":"R21","unstructured":"Johnson D.S. and Garey M.R., Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman (1979)."},{"key":"R22","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0304-3975(87)90067-3","volume":"53","author":"M\u00fcller","year":"1987","journal-title":"Theor. Comput. Sci."},{"key":"R23","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/s12190-020-01345-4","volume":"64","author":"Padamutham","year":"2020","journal-title":"J. Appl. Math. Comput."},{"key":"R24","unstructured":"Peng S.-L. and Tsai Y.-H., Roman domination on graphs of bounded treewidth, in Proceedings of the 24th Workshop on Combinatorial Mathematics and Computation Theory (2007) 128\u2013131."},{"key":"R25","unstructured":"Hsu C.-H., Liu C.-S. and Peng S.-L., Roman domination on block graphs, in Proceedings of the 22nd Workshop on Combinatorial Mathematics and Computation Theory (2005) 188\u2013191."},{"key":"R26","unstructured":"Mahadev N.V.R. and Peled U.N., Threshold Graphs and Related Topics. Elsevier (1995)."},{"key":"R27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4153\/CMB-1963-001-x","volume":"6","author":"Harary","year":"1963","journal-title":"Can. Math. Bull."},{"key":"R28","unstructured":"Aho A.V. and Hopcroft J.E., The Design and Analysis of Computer Algorithms. Pearson Education India (1974)."},{"key":"R29","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1007\/s10878-017-0197-y","volume":"35","author":"Pradhan","year":"2018","journal-title":"J. Comb. Optim."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024038\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T08:18:25Z","timestamp":1719908305000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024038"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7]]},"references-count":29,"journal-issue":{"issue":"4"},"alternative-id":["ro230619"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2024038","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"2804-7303","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7]]}}}