{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:23:38Z","timestamp":1753885418653,"version":"3.41.2"},"reference-count":15,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2023,4]]},"abstract":"<jats:p> For a simple, undirected graph [Formula: see text], a restrained Roman dominating function (rRDF) [Formula: see text] has the property that, every vertex [Formula: see text] with [Formula: see text] is adjacent to at least one vertex v for which [Formula: see text] and at least one vertex [Formula: see text] for which [Formula: see text]. The weight of an rRDF is the sum [Formula: see text]. The minimum weight of an rRDF is called the restrained Roman domination number (rRDN) and is denoted by [Formula: see text]. We show that restrained Roman domination and domination problems are not equivalent in computational complexity aspects. Next, we show that the problem of deciding if G has an rRDF of weight at most l for chordal and bipartite graphs is NP-complete. Finally, we show that rRDN is determined in linear time for bounded treewidth graphs and threshold graphs. <\/jats:p>","DOI":"10.1142\/s1793830922500963","type":"journal-article","created":{"date-parts":[[2022,4,19]],"date-time":"2022-04-19T15:08:03Z","timestamp":1650380883000},"source":"Crossref","is-referenced-by-count":2,"title":["Complexity aspects of restrained Roman domination in graphs"],"prefix":"10.1142","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6589-8358","authenticated-orcid":false,"given":"Padamutham","family":"Chakradhar","sequence":"first","affiliation":[{"name":"Department of Computer Science and Artificial Intelligence, SR University, Warangal, Telangana, India"}]}],"member":"219","published-online":{"date-parts":[[2022,5,10]]},"reference":[{"key":"S1793830922500963BIB001","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.tcs.2005.09.027","volume":"349","author":"Bodlaender H. L.","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"S1793830922500963BIB002","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.disc.2003.06.004","volume":"278","author":"Cockayne E. J.","year":"2004","journal-title":"Discrete Math."},{"key":"S1793830922500963BIB003","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"Courcelle B.","year":"1990","journal-title":"Inf. Comput."},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","year":"1979","author":"Garey M. R.","key":"S1793830922500963BIB004"},{"volume-title":"Domination in Graphs: Advanced Topics","year":"1997","author":"Haynes T. W.","key":"S1793830922500963BIB005"},{"key":"S1793830922500963BIB006","doi-asserted-by":"crossref","DOI":"10.1201\/9781482246582","volume-title":"Fundamentals of Domination in Graphs","author":"Haynes T. W.","year":"2013"},{"key":"S1793830922500963BIB007","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/S0012-365X(03)00040-2","volume":"271","author":"Henning M.","year":"2003","journal-title":"Discrete Math."},{"key":"S1793830922500963BIB009","volume-title":"Threshold Graphs and Related Topics","volume":"56","author":"Mahadev N.","year":"1995"},{"issue":"1","key":"S1793830922500963BIB010","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/s12190-020-01345-4","volume":"64","author":"Padamutham C.","year":"2020","journal-title":"J. Appl. Math. Comput."},{"key":"S1793830922500963BIB011","first-page":"2150063","volume":"13","author":"Padamutham C.","year":"2020","journal-title":"Discrete Math. Algorithms Appl."},{"key":"S1793830922500963BIB012","doi-asserted-by":"crossref","first-page":"1715","DOI":"10.1007\/s41980-020-00468-5","volume":"47","author":"Padamutham C.","year":"2020","journal-title":"Bull. Iranian Math. Soc."},{"issue":"1","key":"S1793830922500963BIB013","first-page":"1","volume":"4","author":"Pushpam R. L.","year":"2015","journal-title":"Trans. Comb."},{"volume-title":"On the Restrained Roman Domination in Graphs","year":"2015","author":"Rad N. J.","key":"S1793830922500963BIB014"},{"issue":"2","key":"S1793830922500963BIB015","first-page":"185","volume":"4","author":"Sheikholeslami S. M.","year":"2019","journal-title":"Commun. Comb. Optim."},{"key":"S1793830922500963BIB016","volume-title":"Introduction to Graph Theory","volume":"2","author":"West D. B.","year":"2001"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830922500963","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,24]],"date-time":"2023-03-24T10:15:43Z","timestamp":1679652943000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S1793830922500963"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,10]]},"references-count":15,"journal-issue":{"issue":"03","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["10.1142\/S1793830922500963"],"URL":"https:\/\/doi.org\/10.1142\/s1793830922500963","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2022,5,10]]},"article-number":"2250096"}}