{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:28:25Z","timestamp":1753885705681,"version":"3.41.2"},"reference-count":22,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:p> For a simple, undirected, connected graph [Formula: see text], a function [Formula: see text] which satisfies the following conditions is called a total Roman {3}-dominating function (TR3DF) of [Formula: see text] with weight [Formula: see text]: <\/jats:p><jats:p> (C1) For every vertex [Formula: see text] if [Formula: see text], then [Formula: see text] has [Formula: see text] ([Formula: see text]) neighbors such that whose sum is at least 3, and if [Formula: see text], then [Formula: see text] has [Formula: see text] ([Formula: see text]) neighbors such that whose sum is at least 2. <\/jats:p><jats:p> (C2) The subgraph induced by the set of vertices labeled one, two or three has no isolated vertices. <\/jats:p><jats:p> For a graph [Formula: see text], the smallest possible weight of a TR3DF of [Formula: see text] denoted [Formula: see text] is known as the total Roman[Formula: see text]-domination number of [Formula: see text]. The problem of determining [Formula: see text] of a graph [Formula: see text] is called minimum total Roman {3}-domination problem (MTR3DP). In this paper, we show that the problem of deciding if [Formula: see text] has a TR3DF of weight at most [Formula: see text] for chordal graphs is NP-complete. We also show that MTR3DP is polynomial time solvable for bounded treewidth graphs, chain graphs and threshold graphs. We design a [Formula: see text]-approximation algorithm for the MTR3DP and show that the same cannot have [Formula: see text] ratio approximation algorithm for any [Formula: see text] unless NP [Formula: see text]. Next, we show that MTR3DP is APX-complete for graphs with [Formula: see text]. We also show that the domination and total Roman {3}-domination problems are not equivalent in computational complexity aspects. Finally, we present an integer linear programming formulation for MTR3DP. <\/jats:p>","DOI":"10.1142\/s1793830921500634","type":"journal-article","created":{"date-parts":[[2020,11,25]],"date-time":"2020-11-25T11:24:51Z","timestamp":1606303491000},"source":"Crossref","is-referenced-by-count":2,"title":["Algorithmic aspects of total Roman {3}-domination in graphs"],"prefix":"10.1142","volume":"13","author":[{"given":"Padamutham","family":"Chakradhar","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, National Institute of Technology, Warangal 506 004, India"}]},{"given":"Palagiri","family":"Venkata Subba Reddy","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, National Institute of Technology, Warangal 506 004, India"}]}],"member":"219","published-online":{"date-parts":[[2020,12,30]]},"reference":[{"key":"S1793830921500634BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00158-3"},{"key":"S1793830921500634BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.07.003"},{"key":"S1793830921500634BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2003.06.004"},{"key":"S1793830921500634BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"S1793830921500634BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.09.043"},{"volume-title":"Computers and Interactability: A Guide to the Theory of NP-Completeness","year":"1979","author":"Garey M. R.","key":"S1793830921500634BIB006"},{"key":"S1793830921500634BIB007","doi-asserted-by":"publisher","DOI":"10.1201\/9781482246582"},{"key":"S1793830921500634BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-6525-6"},{"key":"S1793830921500634BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.09.019"},{"key":"S1793830921500634BIB010","doi-asserted-by":"publisher","DOI":"10.2298\/PIM1613051I"},{"key":"S1793830921500634BIB011","volume-title":"Threshold Graphs and Related Topics","volume":"56","author":"Mahadev N.","year":"1995"},{"key":"S1793830921500634BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2020.02.001"},{"key":"S1793830921500634BIB013","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00334"},{"key":"S1793830921500634BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-017-0112-6"},{"key":"S1793830921500634BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"S1793830921500634BIB016","first-page":"167","volume":"19","author":"Rad N. J.","year":"2019","journal-title":"Ann. Stiint. Univ. Ovidius Const. Ser. Mat."},{"key":"S1793830921500634BIB017","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.2000.12005243"},{"key":"S1793830921500634BIB018","doi-asserted-by":"publisher","DOI":"10.3390\/sym12020268"},{"key":"S1793830921500634BIB019","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30551-4_74"},{"key":"S1793830921500634BIB020","volume-title":"Introduction to Graph Theory","volume":"2","author":"West D. B.","year":"2001"},{"key":"S1793830921500634BIB021","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804355"},{"key":"S1793830921500634BIB022","doi-asserted-by":"publisher","DOI":"10.1145\/1655925.1655948"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830921500634","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,14]],"date-time":"2021-10-14T03:58:57Z","timestamp":1634183937000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830921500634"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,30]]},"references-count":22,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["10.1142\/S1793830921500634"],"URL":"https:\/\/doi.org\/10.1142\/s1793830921500634","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2020,12,30]]},"article-number":"2150063"}}