Algorithmic Aspects of Quasi-Total Roman Domination in Graphs

Document Type : Original paper

Authors

1 National Institute of Technology Warangal

2 Department of Computer Science and Engineering, National Institute of Technology Warangal, India.

Abstract

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.
 
 

Keywords

Main Subjects

References

[1] A. Brandstädt, V.B. Le, and J.P. Spinrad, Graph Classes: A Survey, SIAM, Philadelphia, 1999.
[2] E.J. Cockayne, P.A. Dreyer Jr, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1-3, 11–22.
[3] B. Courcelle, The monadic second-order logic of graphs. i. Recognizable sets of finite graphs, Inf. comput. 85 (1990), no. 1, 12–75.
[4] P.A. Dreyer, Applications and variations of domination in graphs, Ph.D. thesis, Rutgers University, New Jersey, 2000.
[5] O. Favaron, H. Karami, R. Khoeilar, and S.M. Sheikholeslami, On the Roman domination number of a graph, Discrete Math. 309 (2009), no. 10, 3447–3451.
[6] S.C. Garc´ıa, A.C. Martínez, and I.G. Yero, Quasi-total Roman domination in graphs, Results Math. 74 (2019), no. 4, 1–18.
[7] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker Inc., 1998.
[8] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, CRC press, 1998.
[9] M.A. Henning, Defending the Roman Empire from multiple attacks, Discrete Math. 271 (2003), no. 1-3, 101–115.
[10] M.A. Henning and S.T. Hedetniemi, Defending the Roman Empire—A new strategy, Discrete Math. 266 (2003), no. 1-3, 239–251.
[11] Michael Henning, A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002), no. 2, 325–334.
[12] N. Jafari Rad and L. Volkmann, Roman domination perfect graphs, An. Stiint. Univ. Ovidius Constanta Ser. Mat. 19 (2011), 167–174.
[13] T. Kloks, M. Liedloff, J. Liu, and S.L. Peng, Roman domination in some special classes of graphs, Tech. report, TR-MA-04-01, 2004.
[14] M.-S. Lin and C.-M. Chen, Counting independent sets in tree convex bipartite graphs, Discrete Appl. Math. 218 (2017), 113–122.
[15] N.V.R. Mahadev and U.N. Peled, Threshold Graphs and Related Topics, Elsevier, 1995.
[16] C.S. ReVelle and K.E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Amer. Math. Monthly 107 (2000), no. 7, 585–594.
[17] I. Stewart, Defend the Roman empire!, Sci. Am. 281 (1999), no. 6, 136–138.
[18] R. Uehara and Y. Uno, Efficient algorithms for the longest path problem, International symposium on algorithms and computation, Hong Kong, China, Springer, 2004, pp. 871–883.
[19] D.B. West, Introduction to Graph Theory, Second Edition, Prentice Hall, 2001.
[20] M. Yannakakis, The complexity of the partial order dimension problem, SIAM J. Alg. Disc. Meth. 3 (1982), no. 3, 351–358.
Communications in Combinatorics and Optimization
Volume 7, Issue 1
June 2022
Pages 93-104

Files

Share

How to cite

Statistics