{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T09:06:08Z","timestamp":1777539968087,"version":"3.51.4"},"reference-count":30,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2022,2,18]],"date-time":"2022-02-18T00:00:00Z","timestamp":1645142400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>For a graph G=(V,E), an independent Roman dominating function (IRDF) is a function f:V\u2192{0,1,2} having the property that: (1) every vertex assigned a value of 0 is adjacent to at least one vertex assigned a value of 2, (2) there are no two adjacent vertices with positive assignments. The weight of an IRDF (w(f)) is the sum of assignments for all vertices. The minimum weight of an independent Roman dominating function on graph G is the independent Roman domination number, denoted by iR(G). In this paper, we prove that the decision problem of minimum IRDF is NP-complete for chordal bipartite graphs. Then, we research the difference in complexity between the decision problem of RDF and IRDF. Finally, we propose a linear-time algorithm for computing the minimum weight of an independent Roman dominating function in trees.<\/jats:p>","DOI":"10.3390\/sym14020404","type":"journal-article","created":{"date-parts":[[2022,2,21]],"date-time":"2022-02-21T08:34:47Z","timestamp":1645432487000},"page":"404","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Independent Roman Domination: The Complexity and Linear-Time Algorithm for Trees"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9011-6653","authenticated-orcid":false,"given":"Zhixing","family":"Duan","sequence":"first","affiliation":[{"name":"Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3316-877X","authenticated-orcid":false,"given":"Huiqin","family":"Jiang","sequence":"additional","affiliation":[{"name":"Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5241-0912","authenticated-orcid":false,"given":"Xinyue","family":"Liu","sequence":"additional","affiliation":[{"name":"Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1179-5748","authenticated-orcid":false,"given":"Pu","family":"Wu","sequence":"additional","affiliation":[{"name":"School of Electronic Engineering and Computer Science, Peking University, Beijing 100871, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0764-4135","authenticated-orcid":false,"given":"Zehui","family":"Shao","sequence":"additional","affiliation":[{"name":"Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,2,18]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1038\/scientificamerican1299-136","article-title":"Defend the Roman Empire!","volume":"281","author":"Stewart","year":"1999","journal-title":"Sci. Am."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.disc.2003.06.004","article-title":"Roman domination in graphs","volume":"278","author":"Cockayne","year":"2004","journal-title":"Discret. Math."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"771","DOI":"10.7151\/dmgt.2142","article-title":"Extremal Graphs for a Bound on the Roman Domination Number","volume":"40","author":"Blidia","year":"2020","journal-title":"Discuss. Math. Graph Theory"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1575","DOI":"10.1137\/070699688","article-title":"Extremal problems for roman domination","volume":"23","author":"Chambers","year":"2009","journal-title":"Siam J. Discret. Math."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/080733085","article-title":"Roman Domination On 2-Connected Graphs","volume":"26","author":"Liu","year":"2012","journal-title":"Siam J. Discret. Math."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1386","DOI":"10.1016\/j.disc.2011.12.021","article-title":"Upper bounds on Roman domination numbers of graphs","volume":"312","author":"Liu","year":"2012","journal-title":"Discret. Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"3338","DOI":"10.1016\/j.disc.2006.06.018","article-title":"A note on Roman domination in graphs","volume":"306","author":"Xing","year":"2006","journal-title":"Discret. Math."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"155","DOI":"10.2298\/AADM140210003B","article-title":"The Differential And The Roman Domination Number Of A Graph","volume":"8","author":"Bermudo","year":"2014","journal-title":"Appl. Anal. Discret. Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1080\/00207160701374376","article-title":"Roman domination: A parameterized perspective","volume":"85","author":"Fernau","year":"2008","journal-title":"Int. J. Comput. Math."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"3400","DOI":"10.1016\/j.dam.2008.01.011","article-title":"Efficient algorithms for Roman domination on some classes of graphs","volume":"156","author":"Liedloff","year":"2008","journal-title":"Discret. Appl. Math."},{"key":"ref_11","first-page":"125444","article-title":"Triple Roman domination in graphs","volume":"391","author":"Ahangar","year":"2021","journal-title":"Appl. Math. Comput."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Ahangar, H.A., Amjadi, J., Chellali, M., Nazari-Moghaddam, S., and Sheikholeslami, S.M. (2019). Total Roman reinforcement in graphs. Discuss. Math. Graph Theory, 39.","DOI":"10.7151\/dmgt.2108"},{"key":"ref_13","first-page":"126662","article-title":"Maximal double Roman domination in graphs","volume":"414","author":"Ahangar","year":"2022","journal-title":"Appl. Math. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/j.dam.2021.01.021","article-title":"A note on domination number in maximal outerplanar graphs","volume":"293","author":"Liu","year":"2021","journal-title":"Discret. Appl. Math."},{"key":"ref_15","unstructured":"Berge, C. (1962). Theory of Graphs and Its Applications [Russian Translation], IL."},{"key":"ref_16","unstructured":"Berge, C. (1973). Graphs and Hypergraphs, North-Holland Mathematical Library."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"2314","DOI":"10.1016\/j.disc.2005.12.029","article-title":"Extremal graphs for a new upper bound on domination parameters in graphs","volume":"306","author":"Blidia","year":"2006","journal-title":"Discret. Math."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1002\/jgt.3190030306","article-title":"Graph-theoretic parameters concerning domination, independence, and irredundance","volume":"3","author":"Cockayne","year":"1979","journal-title":"J. Graph Theory"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"959","DOI":"10.1016\/j.aml.2003.09.006","article-title":"A note on connected bipartite graphs having independent domination number half their order","volume":"17","author":"Ma","year":"2004","journal-title":"Appl. Math. Lett."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1007\/BF02759743","article-title":"Independent sets in regular graphs","volume":"2","author":"Rosenfeld","year":"1964","journal-title":"Isr. J. Math."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0166-218X(84)90088-X","article-title":"Clustering and domination in perfect graphs","volume":"9","author":"Corneil","year":"1984","journal-title":"Discret. Appl. Math."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","article-title":"Unit disk graphs","volume":"86","author":"Clark","year":"1990","journal-title":"Discret. Math."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0166-218X(98)00147-4","article-title":"On the algorithmic complexity of twelve covering and independence parameters of graphs","volume":"91","author":"Manlove","year":"1999","journal-title":"Discret. Appl. Math."},{"key":"ref_24","first-page":"3","article-title":"Independent domination in trees","volume":"19","author":"Beyer","year":"1977","journal-title":"Congr. Numer"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1137\/S0895480194275825","article-title":"Algorithms for vertex partitioning problems on partial k-trees","volume":"10","author":"Telle","year":"1997","journal-title":"SIAM J. Discret. Math."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/0167-6377(82)90015-3","article-title":"Independent domination in chordal graphs","volume":"1","author":"Farber","year":"1982","journal-title":"Oper. Res. Lett."},{"key":"ref_27","first-page":"11","article-title":"Properties of independent Roman domination in graphs","volume":"52","author":"Rad","year":"2012","journal-title":"Australas. J. Comb."},{"key":"ref_28","first-page":"119","article-title":"Note on the Independent Roman Domination Number of a Graph","volume":"95","author":"Rad","year":"2015","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"337","DOI":"10.7151\/dmgt.1669","article-title":"Strong Equality Between the Roman Domination and Independent Roman Domination Numbers in Trees","volume":"33","author":"Chellali","year":"2013","journal-title":"Discuss. Math. Graph Theory"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"74737","DOI":"10.1109\/ACCESS.2018.2883028","article-title":"Independent Roman Domination Stable and Vertex-Critical Graphs","volume":"6","author":"Wu","year":"2018","journal-title":"IEEE Access"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/14\/2\/404\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:22:04Z","timestamp":1760134924000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/14\/2\/404"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,18]]},"references-count":30,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2022,2]]}},"alternative-id":["sym14020404"],"URL":"https:\/\/doi.org\/10.3390\/sym14020404","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,18]]}}}