Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287120220601Algorithmic Aspects of Quasi-Total Roman Domination in Graphs931041422010.22049/cco.2021.27126.1200ENVenkata Subba ReddyPNational Institute of Technology WarangalMangalVikasDepartment of Computer Science and Engineering, National Institute of Technology Warangal, India.Journal Article20210208For a simple, undirected, connected graph $G$($V,E$), a function $f : V(G) rightarrow lbrace 0, 1, 2 rbrace$ which satisfies the following conditions is called a quasi-total Roman dominating function (QTRDF) of $G$ with weight $f(V(G))=sum_{v in V(G)} f(v)$.<br /> C1). Every vertex $u in V(G)$ for which $f(u) = 0$ must be adjacent to at least one vertex $v$ with $f(v) = 2$, and <br /> C2). Every vertex $u in V(G)$ for which $f(u) = 2$ must be adjacent to at least one vertex $v$ with $f(v) geq 1$. <br /> For a graph $G$, the smallest possible weight of a QTRDF of $G$ denoted $gamma_{qtR}(G)$ is known as the textit{quasi-total Roman domination number} of $G$.<br /> The problem of determining $gamma_{qtR}(G)$ of a graph $G$ is called minimum quasi-total Roman domination problem (MQTRDP).<br /> In this paper, we show that the problem of determining whether $G$ has a QTRDF of weight at most $l$ is NP-complete for split graphs, star convex bipartite graphs, comb convex bipartite graphs and planar graphs.<br /> On the positive side, we show that MQTRDP for threshold graphs, chain graphs and bounded treewidth graphs is linear time solvable. Finally, an integer linear programming formulation for MQTRDP is presented.<br /> <br /> http://comb-opt.azaruniv.ac.ir/article_14220_e1aeb63f7a60db0a40f1bdb4295ae39a.pdf