Communications in Combinatorics and Optimization | |
Algorithmic Aspects of Quasi-Total Roman Domination in Graphs | |
article | |
P, Venkata Subba Reddy1  Vikas, Mangal2  | |
[1] National Institute of Technology Warangal;Department of Computer Science and Engineering, National Institute of Technology Warangal | |
关键词: Domination number; quasi-total Roman domination; complexity classes; graph classes; linear programming; | |
DOI : 10.22049/cco.2021.27126.1200 | |
学科分类:社会科学、人文和艺术(综合) | |
来源: Azarbaijan Shahide Madani Universit | |
【 摘 要 】
For a simple, undirected, connected graph G(V, E), a function f : V (G) →{0, 1, 2} which satisfies the following conditions is called a quasi-total Roman dominating function (QTRDF) of G with weight f(V (G)) = Pv∈V (G)f(v).C1). Every vertex u ∈ V (G) for which f(u) = 0 must be adjacent to at least one vertexv with f(v) = 2, andC2). Every vertex u ∈ V (G) for which f(u) = 2 must be adjacent to at least one vertexv with f(v) ≥ 1.For a graph G, the smallest possible weight of a QTRDF of G denoted γqtR(G) isknown as the quasi-total Roman domination number of G. The problem of determining γ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 hasa QTRDF of weight at most l is NP-complete for split graphs, star convex bipartitegraphs, comb convex bipartite graphs and planar graphs. On the positive side, we showthat MQTRDP for threshold graphs, chain graphs and bounded treewidth graphs islinear time solvable. Finally, an integer linear programming formulation for MQTRDPis presented.
【 授权许可】
CC BY-SA
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO202303290003891ZK.pdf | 432KB | download |