TY - JOUR ID - 14220 TI - Algorithmic Aspects of Quasi-Total Roman Domination in Graphs JO - Communications in Combinatorics and Optimization JA - CCO LA - en SN - 2538-2128 AU - P, Venkata Subba Reddy AU - Vikas, Mangal AD - National Institute of Technology Warangal AD - Department of Computer Science and Engineering, National Institute of Technology Warangal, India. Y1 - 2022 PY - 2022 VL - 7 IS - 1 SP - 93 EP - 104 KW - Domination number KW - quasi-total Roman domination KW - complexity classes KW - graph classes KW - linear programming DO - 10.22049/cco.2021.27126.1200 N2 - For 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)$.    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     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$.     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$.    The problem of determining  $\gamma_{qtR}(G)$ of a graph $G$ is called minimum quasi-total Roman domination problem (MQTRDP).    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.    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.   UR - http://comb-opt.azaruniv.ac.ir/article_14220.html L1 - http://comb-opt.azaruniv.ac.ir/article_14220_e1aeb63f7a60db0a40f1bdb4295ae39a.pdf ER -