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 -