{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:27:46Z","timestamp":1740144466260,"version":"3.37.3"},"reference-count":17,"publisher":"EDP Sciences","issue":"3","license":[{"start":{"date-parts":[[2023,5,18]],"date-time":"2023-05-18T00:00:00Z","timestamp":1684368000000},"content-version":"vor","delay-in-days":17,"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,23]]},"published-print":{"date-parts":[[2023,5]]},"abstract":"For an integer k<\/jats:italic>\u00a0\u2265\u00a01, a Roman {k<\/jats:italic>}-dominating function (R{k<\/jats:italic>}DF) on a graph G<\/jats:italic>\u00a0=\u00a0(V<\/jats:italic>,\u00a0E<\/jats:italic>) is a function f<\/jats:italic>\u00a0:\u00a0V<\/jats:italic>\u00a0\u2192\u00a0{0,\u00a01,\u00a0\u2026,\u00a0k<\/jats:italic>} such that for every vertex v<\/jats:italic>\u00a0\u2208\u00a0V<\/jats:italic> with f<\/jats:italic>(v<\/jats:italic>)\u00a0=\u00a00, \u2211u<\/jats:italic>\u2208N<\/jats:italic>(v<\/jats:italic>)<\/jats:sub>\u00a0f<\/jats:italic>(u<\/jats:italic>)\u00a0\u2265\u00a0k<\/jats:italic>, where N<\/jats:italic>(v<\/jats:italic>) is the set of vertices adjacent to v<\/jats:italic>. The weight of an R{k<\/jats:italic>}DF is the sum of its function values over the whole set of vertices, and the Roman {k<\/jats:italic>}-domination number \u03b3<\/jats:italic>{kR<\/jats:italic>}<\/jats:sub>(G<\/jats:italic>) is the minimum weight of an R{k<\/jats:italic>}DF on G<\/jats:italic>. In this paper, we will be focusing on the case k<\/jats:italic>\u00a0=\u00a03, where trivially for every connected graphs of order n<\/jats:italic>\u00a0\u2265\u00a03, 3\u00a0\u2264\u00a0\u03b3<\/jats:italic>{kR<\/jats:italic>}<\/jats:sub>(G<\/jats:italic>)\u00a0\u2264n<\/jats:italic>. We characterize all connected graphs G<\/jats:italic> of order n<\/jats:italic>\u00a0\u2265\u00a03 such that \u03b3<\/jats:italic>{3R<\/jats:italic>}<\/jats:sub>(G<\/jats:italic>)\u00a0\u2208\u00a0{3, n<\/jats:italic>\u00a0\u2212\u00a01,\u00a0n<\/jats:italic>}, and we improve the previous lower and upper bounds. Moreover, we show that for every tree T<\/jats:italic> of order n<\/jats:italic>\u00a0\u2265\u00a03, \u03b3<\/jats:italic>{3R<\/jats:italic>}<\/jats:sub>(T<\/jats:italic>)\u00a0\u2265\u00a0\u03b3<\/jats:italic>(T<\/jats:italic>)\u00a0+\u00a02, where \u03b3<\/jats:italic>(T<\/jats:italic>) is the domination number of T<\/jats:italic>, and we characterize the trees attaining this bound.<\/jats:p>","DOI":"10.1051\/ro\/2023058","type":"journal-article","created":{"date-parts":[[2023,4,27]],"date-time":"2023-04-27T19:05:01Z","timestamp":1682622301000},"page":"1195-1208","source":"Crossref","is-referenced-by-count":0,"title":["Graphs with small or large Roman {3}-domination number"],"prefix":"10.1051","volume":"57","author":[{"given":"Nafiseh","family":"Ebrahimi","sequence":"first","affiliation":[]},{"given":"Hossein","family":"Abdollahzadeh Ahangar","sequence":"additional","affiliation":[]},{"given":"Mustapha","family":"Chellali","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2298-4744","authenticated-orcid":false,"given":"Seyed Mahmoud","family":"Sheikholeslami","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2023,5,18]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"1111","DOI":"10.1007\/s41980-021-00565-z","volume":"48","author":"Abdollahzadeh Ahangar","year":"2022","journal-title":"Bull. Iran. Math. Soc."},{"key":"R2","doi-asserted-by":"crossref","first-page":"937","DOI":"10.7151\/dmgt.2316","volume":"42","author":"Abdollahzadeh Ahangar","year":"2022","journal-title":"Discuss. Math. Graph Theory"},{"key":"R3","doi-asserted-by":"crossref","first-page":"213","DOI":"10.11650\/twjm\/1500602498","volume":"12","author":"Bre\u0161ar","year":"2008","journal-title":"Taiwanese J. Math."},{"key":"R4","doi-asserted-by":"crossref","first-page":"1395","DOI":"10.1016\/j.dam.2013.01.024","volume":"161","author":"Chang","year":"2013","journal-title":"Discrete Appl. Math."},{"key":"R5","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":"R6","doi-asserted-by":"crossref","unstructured":"Chellali M., Jafari Rad N., 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, Berlin\/Heidelberg (2020) 365\u2013409.","DOI":"10.1007\/978-3-030-51117-3_11"},{"key":"R7","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":"R8","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, Berlin\/Heidelberg (2021) 273\u2013307.","DOI":"10.1007\/978-3-030-58892-2_10"},{"key":"R9","doi-asserted-by":"crossref","first-page":"4273","DOI":"10.1007\/s40840-020-00921-y","volume":"43","author":"Haynes","year":"2020","journal-title":"Bull. Malays. Math. Sci. Soc."},{"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":"257","volume":"7","author":"Lyle","year":"2022","journal-title":"Commun. Comb. Optim."},{"key":"R12","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1051\/ro\/2021022","volume":"55","author":"Samadi","year":"2021","journal-title":"RAIRO-Oper. Res."},{"key":"R13","unstructured":"Sheikholeslami S.M. and Volkmann L., Total Italian domatic number of graphs. Comput. Sci. J. Moldova (to appear)."},{"key":"R14","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/j.ins.2013.07.020","volume":"254","author":"Shao","year":"2014","journal-title":"Inf. Sci."},{"key":"R15","first-page":"183","volume":"8","author":"Volkmann","year":"2023","journal-title":"Commun. Comb. Optim."},{"key":"R16","first-page":"1","volume":"8","author":"Volkmann","year":"2023","journal-title":"Commun. Comb. Optim."},{"key":"R17","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1007\/s10878-021-00735-z","volume":"42","author":"Wang","year":"2021","journal-title":"J. Comb. Optim."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023058\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,18]],"date-time":"2023-05-18T08:15:52Z","timestamp":1684397752000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023058"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5]]},"references-count":17,"journal-issue":{"issue":"3"},"alternative-id":["ro220361"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2023058","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2023,5]]}}}