{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:29Z","timestamp":1740144509651,"version":"3.37.3"},"reference-count":25,"publisher":"EDP Sciences","license":[{"start":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T00:00:00Z","timestamp":1614643200000},"content-version":"vor","delay-in-days":60,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"funder":[{"DOI":"10.13039\/501100006011","name":"Babol Noshirvani University of Technology","doi-asserted-by":"publisher","award":["BNUT\/385001\/99"],"award-info":[{"award-number":["BNUT\/385001\/99"]}],"id":[{"id":"10.13039\/501100006011","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2020,4,15]]},"published-print":{"date-parts":[[2021]]},"abstract":"<jats:p>Let <jats:italic>G<\/jats:italic> = (<jats:italic>V, E<\/jats:italic>) be a simple graph with vertex setxs <jats:italic>V<\/jats:italic> and edge set <jats:italic>E<\/jats:italic>. A mixed Roman dominating function of <jats:italic>G<\/jats:italic> is a function <jats:italic>f<\/jats:italic> : <jats:italic>V<\/jats:italic> \u222a <jats:italic>E<\/jats:italic> \u2192 {0, 1, 2} satisfying the condition that every element <jats:italic>x<\/jats:italic> \u2208 <jats:italic>V<\/jats:italic> \u222a <jats:italic>E<\/jats:italic> for which <jats:italic>f(x)<\/jats:italic> = 0 is adjacent or incident to at least one element <jats:italic>y<\/jats:italic> \u2208 <jats:italic>V<\/jats:italic> \u222a <jats:italic>E<\/jats:italic> for which <jats:italic>f(y)<\/jats:italic> = 2. The weight of a mixed Roman dominating function <jats:italic>f<\/jats:italic> is \u03c9(<jats:italic>f<\/jats:italic>) = \u2211<jats:sub><jats:italic>x<\/jats:italic>\u2208<jats:italic>V<\/jats:italic>\u222a<jats:italic>E<\/jats:italic><\/jats:sub> <jats:italic>f(x)<\/jats:italic>. The mixed Roman domination number \u03b3<jats:italic><jats:sub>R<\/jats:sub><\/jats:italic>(<jats:italic>G<\/jats:italic>) of <jats:italic>G<\/jats:italic> is the minimum weight of a mixed Roman dominating function of <jats:italic>G<\/jats:italic>. We first show that the problem of computing \u03b3<jats:italic><jats:sub>R<\/jats:sub><jats:sup>*<\/jats:sup><\/jats:italic>(<jats:italic>G<\/jats:italic>) is NP-complete for bipartite graphs and then we present upper and lower bounds on the mixed Roman domination number, some of them are for the class of trees.<\/jats:p>","DOI":"10.1051\/ro\/2020038","type":"journal-article","created":{"date-parts":[[2020,4,17]],"date-time":"2020-04-17T17:28:03Z","timestamp":1587144483000},"page":"S1411-S1423","source":"Crossref","is-referenced-by-count":2,"special_numbering":"Supplement","title":["Some progress on the mixed roman domination in graphs"],"prefix":"10.1051","volume":"55","author":[{"given":"Hossein Abdollahzadeh","family":"Ahangar","sequence":"first","affiliation":[]},{"given":"Jafar","family":"Amjadi","sequence":"additional","affiliation":[]},{"given":"Mustapha","family":"Chellali","sequence":"additional","affiliation":[]},{"given":"Saeed","family":"Kosari","sequence":"additional","affiliation":[]},{"given":"Vladimir","family":"Samodivkin","sequence":"additional","affiliation":[]},{"given":"Seyed Mahmoud","family":"Sheikholeslami","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2021,3,2]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.dam.2018.09.009","volume":"257","author":"Ahangar","year":"2019","journal-title":"Disc. Appl. Math"},{"key":"R2","first-page":"124617","volume":"364","author":"Ahangar","year":"2020","journal-title":"Appl. Math. Comput"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Ahangar H. Abdollahzadeh, Chellali M., Sheikholeslami S.M. and Valenzuela-Tripodoro J.C., Total Roman {2}-domination in graphs. Discuss. Math. Graph Theory (to appear) DOI: https:\/\/doi.org\/10.7151\/dmgt.2316 (2020).","DOI":"10.7151\/dmgt.2316"},{"key":"R4","doi-asserted-by":"crossref","first-page":"1443","DOI":"10.1007\/s40840-015-0141-1","volume":"40","author":"Ahangar","year":"2017","journal-title":"Bull. Malays. Math. Sci. Soc"},{"key":"R5","first-page":"11","volume":"52","author":"Adabi","year":"2012","journal-title":"Australas. J. Comb"},{"key":"R6","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1002\/jgt.3190010209","volume":"1","author":"Alavi","year":"1977","journal-title":"J. Graph Theory"},{"key":"R7","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0012-365X(92)90643-T","volume":"100","author":"Alavi","year":"1992","journal-title":"Disc. Math"},{"key":"R8","first-page":"157","volume":"5","author":"Amjadi","year":"2020","journal-title":"Commun. Comb. Optim"},{"key":"R9","unstructured":"Bange D., Barkauskas A.E. and Slater P.J., Efficient dominating sets in graphs, edited by Ringeisen R.D. and Roberts F.S.. In: Applications of Discrete Math. SIAM, Philadelphia, PA (1988) 189\u2013199."},{"key":"R10","doi-asserted-by":"crossref","first-page":"155","DOI":"10.2298\/AADM140210003B","volume":"8","author":"Bermudo","year":"2014","journal-title":"Appl. Anal. Disc. Math"},{"key":"R11","doi-asserted-by":"crossref","first-page":"715","DOI":"10.7494\/OpMath.2012.32.4.715","volume":"32","author":"Chellali","year":"2012","journal-title":"Opuscula Math"},{"key":"R12","doi-asserted-by":"crossref","first-page":"337","DOI":"10.7151\/dmgt.1669","volume":"33","author":"Chellali","year":"2013","journal-title":"Discuss. Math. Graph Theory"},{"key":"R13","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.disc.2003.06.004","volume":"278","author":"Cockayne","year":"2004","journal-title":"Disc. Math"},{"key":"R14","first-page":"351","volume":"80","author":"Targhi","year":"2012","journal-title":"J. Comb. Math. Comb. Comput"},{"key":"R15","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0012-365X(77)90102-9","volume":"19","author":"Erd\u00f6s","year":"1977","journal-title":"Disc. Math"},{"key":"R16","first-page":"27","volume":"5","author":"Hao","year":"2020","journal-title":"Commun. Comb. Optim"},{"key":"R17","first-page":"55","volume":"101","author":"Gunther","year":"1994","journal-title":"Congr. Numer"},{"key":"R18","doi-asserted-by":"crossref","first-page":"553","DOI":"10.7151\/dmgt.1380","volume":"27","author":"Hatami","year":"2007","journal-title":"Discuss. Math. Graph Theory"},{"key":"R19","unstructured":"Haynes T.W., Hedetniemi S.T. and Slater P.J., Fundamentals of Domination in Graphs. Marcel Dekker, New York, NY (1998)."},{"key":"R20","first-page":"129","volume":"217","author":"Hedetniemi","year":"2013","journal-title":"Congr. Numer"},{"key":"R21","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1016\/j.tcs.2012.11.035","volume":"476","author":"Lan","year":"2013","journal-title":"Theor. Comput. Sci"},{"key":"R22","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1080\/00029890.2000.12005243","volume":"107","author":"ReVelle","year":"2000","journal-title":"Am. Math. Mon"},{"key":"R23","first-page":"399","volume":"54","author":"Sampathkumar","year":"1992","journal-title":"Sankay\u0101: Indian J. Stat"},{"key":"R24","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1038\/scientificamerican1299-136","volume":"281","author":"Stewart","year":"1999","journal-title":"Sci. Am"},{"key":"R25","first-page":"111","volume":"5","author":"Volkmann","year":"2020","journal-title":"Commun. Comb. Optim"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2020038\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T09:21:24Z","timestamp":1614676884000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2020038"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"references-count":25,"alternative-id":["ro180193"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2020038","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"1290-3868"}],"subject":[],"published":{"date-parts":[[2021]]}}}