{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:27:48Z","timestamp":1740144468856,"version":"3.37.3"},"reference-count":27,"publisher":"EDP Sciences","issue":"2","license":[{"start":{"date-parts":[[2024,5,3]],"date-time":"2024-05-03T00:00:00Z","timestamp":1714694400000},"content-version":"vor","delay-in-days":63,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11701542"],"award-info":[{"award-number":["11701542"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2023,8,21]]},"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:p>A total Roman {2}-dominating function (TR2DF) on a graph <jats:italic>G<\/jats:italic> with vertex set <jats:italic>V<\/jats:italic> is a function <jats:italic>f<\/jats:italic> : <jats:italic>V<\/jats:italic> \u2192 {0, 1, 2} having the property that for every vertex <jats:italic>v<\/jats:italic> with <jats:italic>f<\/jats:italic>(<jats:italic>v<\/jats:italic>) = 0, \u2211<jats:sub><jats:italic>u\u2208N (v)<\/jats:italic><\/jats:sub> <jats:italic>f<\/jats:italic>(<jats:italic>u<\/jats:italic>) \u2265 2, where <jats:italic>N<\/jats:italic>(<jats:italic>v<\/jats:italic>) represents the open neighborhood of <jats:italic>v<\/jats:italic>, and the subgraph of <jats:italic>G<\/jats:italic> induced by the set of vertices with <jats:italic>f<\/jats:italic>(<jats:italic>v<\/jats:italic>) &gt; 0 has no isolated vertex. The weight of a TR2DF <jats:italic>f<\/jats:italic> is the value <jats:italic>w<\/jats:italic>(<jats:italic>f<\/jats:italic>) = \u2211<jats:sub><jats:italic>v\u2208V<\/jats:italic><\/jats:sub> <jats:italic>f<\/jats:italic>(<jats:italic>v<\/jats:italic>), and the minimum weight of a TR2DF of <jats:italic>G<\/jats:italic> is the total Roman {2}-domination number <jats:italic>\u03b3<\/jats:italic><jats:sub>tR2<\/jats:sub>(<jats:italic>G<\/jats:italic>). The total Roman {2}-domination problem (TR2DP) is to determine the value <jats:italic>\u03b3<\/jats:italic><jats:sub>tR2<\/jats:sub>(<jats:italic>G<\/jats:italic>). In this paper, we first propose an integer linear programming (ILP) formulation for the TR2DP. Furthermore, we apply the discharging approach to determine the total Roman {2}-domination number for some Cartesian products of paths and cycles.<\/jats:p>","DOI":"10.1051\/ro\/2023121","type":"journal-article","created":{"date-parts":[[2023,9,2]],"date-time":"2023-09-02T18:57:43Z","timestamp":1693681063000},"page":"2029-2044","source":"Crossref","is-referenced-by-count":0,"title":["Algorithmic aspect on total Roman {2}-domination of Cartesian products of paths and cycles"],"prefix":"10.1051","volume":"58","author":[{"given":"Qin","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2024,5,3]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Abdollahzadeh Ahangar H., Chellali M., Hajjari M. and Sheikholeslami S.M., Further progress on the total Roman {2}-domination number of graphs. Bull. Iran. Math. Soc. 48 (2022) 1111\u20131119.","DOI":"10.1007\/s41980-021-00565-z"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Abdollahzadeh Ahangar H., Chellali M., Sheikholeslami S.M. and Valenzuela-Tripodoro J.C., Total Roman {2}-dominating functions in graphs. Discuss. Math. Graph Theory 42 (2022) 937\u2013958.","DOI":"10.7151\/dmgt.2316"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Bre\u0161ar B., Henning M.A. and Rall D.F., Rainbow domination in graphs. Taiwanese J. Math. 12 (2008) 213\u2013225.","DOI":"10.11650\/twjm\/1500602498"},{"key":"R4","unstructured":"Burger A.P., de Villiers A.P. and van Vuuren J.H., A binary programming approach towards achieving effective graph protection, in Proceedings of the 2013 ORSSA Annual Conference. ORSSA (2013) 19\u201330."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Cai Q., Fan N., Shi Y. and Yao S., Integer linear programming formulations for double roman domination problem. Optim. Methods Softw. 37 (2022) 1\u201322.","DOI":"10.1080\/10556788.2019.1679142"},{"key":"R6","unstructured":"Chakradhar P. and Subba Reddy P. Venkata, Algorithmic aspects of total Roman {2}-domination in graphs. Commun. Comb. Optim. 7 (2022) 183\u2013192."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Chambers E.W., Kinnersley B., Prince N. and West D.B., Extremal problems for Roman domination. SIAM J. Discrete Math. 23 (2009) 1575\u2013158.","DOI":"10.1137\/070699688"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Chellali M., Haynes T.W., Hedetniemi S.T. and McRae A., Roman {2}-domination. Discrete Appl. Math. 204 (2016) 22\u201328.","DOI":"10.1016\/j.dam.2015.11.013"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Chellali M., Rad N.J., 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 (2020) 365\u2013409.","DOI":"10.1007\/978-3-030-51117-3_11"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Chellali M., Jafari Rad N., Sheikholeslami S.M. and Volkmann L., Varieties of Roman domination II. AKCE Int. J. Graphs Comb. 17 (2020) 966\u2013984.","DOI":"10.1016\/j.akcej.2019.12.001"},{"key":"R11","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 (2021) 273\u2013307.","DOI":"10.1007\/978-3-030-58892-2_10"},{"key":"R12","unstructured":"Chen Q., Semitotal domination numbers of grids, tori and cylinders. Util. Math. 116 (2020) 177\u2013201."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Cockayne E.J., Dreyer P.A., Hedetniemi S.M. and Hedetniemi S.T., Roman domination in graphs. Discrete Math. 278 (2004) 11\u201322.","DOI":"10.1016\/j.disc.2003.06.004"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Favaron O., Karami H., Khoeilar R. and Sheikholeslami S.M., On the Roman domination number of a graph. Discrete Math. 309 (2009) 3447\u20133451.","DOI":"10.1016\/j.disc.2008.09.043"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Garc\u00eda S.C., Mart\u00ednez A.C., Hern\u00e1ndez Mira F.A. and Yero I.G., Total Roman {2}-domination in graphs. Quaestiones Math. 44 (2021) 411\u2013434.","DOI":"10.2989\/16073606.2019.1695230"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"Gravier S. and Mollard M., On domination numbers of Cartesian product of paths. Discrete Appl. Math. 80 (1997) 247\u2013250.","DOI":"10.1016\/S0166-218X(97)00091-7"},{"key":"R17","unstructured":"Harary F. and Haynes T.W., Double domination in graphs. ARS Comb. 55 (2000) 201\u2013213."},{"key":"R18","doi-asserted-by":"crossref","unstructured":"Henning M.A. and Klostermeyer W.F., Italian domination in trees. Discrete Appl. Math. 217 (2017) 557\u2013564.","DOI":"10.1016\/j.dam.2016.09.035"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Ivanovi\u0107 M., Improved integer linear programming formulation for weak Roman domination problem. Soft Comput. 22 (2018) 6583\u20136593.","DOI":"10.1007\/s00500-017-2706-4"},{"key":"R20","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1155\/2021\/5515250","volume":"2021","author":"Kheibari","year":"2021","journal-title":"J. Math."},{"key":"R21","doi-asserted-by":"crossref","unstructured":"Li Z., Shao Z. and Xu J., Weak {2}-domination number of Cartesian products of cycles. J. Comb. Optim. 35 (2018) 75\u201385.","DOI":"10.1007\/s10878-017-0157-6"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"Liu C.H. and Chang G.J., Roman domination on strongly chordal graphs. J. Comb. Optim. 26 (2013) 608\u2013619.","DOI":"10.1007\/s10878-012-9482-y"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Mart\u00ednez A.C., Garc\u00eda S.C. and Rodr\u00edguez-Vel\u00e1zquez J.A., Double domination in lexicographic product graphs. Discrete Appl. Math. 284 (2020) 290\u2013300.","DOI":"10.1016\/j.dam.2020.03.045"},{"key":"R24","unstructured":"Rad N.J. and Volkmann L., Changing and unchanging the Roman domination number of a graph. Util. Math. 89 (2012) 79\u201395."},{"key":"R25","doi-asserted-by":"crossref","unstructured":"ReVelle C.S. and Rosing K.E., Defendens imperium romanum: a classical problem in military strategy. Amer. Math. Monthly 107 (2000) 585\u2013594.","DOI":"10.1080\/00029890.2000.12005243"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"Sheikholeslami S.M. and Volkmann L., Nordhaus\u2013Gaddum type inequalities on the total Italian domination number in graphs. RAIRO: Oper. Res. 56 (2022) 2235\u20132243.","DOI":"10.1051\/ro\/2022108"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"Stewart I., Defend the Roman empire. Sci. Am. 281 (1999) 136\u2013139.","DOI":"10.1038\/scientificamerican1299-136"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023121\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,3]],"date-time":"2024-05-03T08:01:06Z","timestamp":1714723266000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023121"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3]]},"references-count":27,"journal-issue":{"issue":"2"},"alternative-id":["ro230007"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2023121","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2024,3]]}}}