Vertex-edge Roman domination in graphs: complexity and algorithms

Document Type : Original paper

Authors

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

Abstract

For a simple, undirected graph $G(V,E)$, a function $h : V(G) \rightarrow \lbrace 0, 1, 2\rbrace$ such that each edge $ (u,v)$ of $G$ is either incident with a vertex with weight at least one or there exists a vertex $w$ such that either $(u,w) \in E(G)$ or  $(v,w) \in E(G)$ and $h(w) = 2$, is called a vertex-edge Roman dominating function (ve-RDF) of $G$. For a graph $G$, the smallest possible weight of a ve-RDF of $G$ which is denoted by $\gamma_{veR}(G)$, is known as the \textit{vertex-edge Roman domination number} of $G$. The problem of determining  $\gamma_{veR}(G)$ of a graph $G$ is called minimum vertex-edge Roman domination problem (MVERDP). In this article, we show that the problem of deciding if $G$ has a ve-RDF of weight at most $l$ for star convex bipartite graphs, comb convex bipartite graphs, chordal graphs and planar graphs is NP-complete. On the positive side, we show that MVERDP is linear time solvable for threshold graphs, chain graphs and bounded tree-width graphs. On the approximation point of view, a 2-approximation algorithm for MVERDP is presented. It is also shown that vertex cover and vertex-edge Roman domination problems are not equivalent in computational complexity aspects. Finally, an integer linear programming  formulation for MVERDP is presented.

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar, Maximal Roman domination numbers in graphs, Util. Math. 103 (2017), 245–258.
[2] H. Abdollahzadeh Ahangar, M.P. Alvarez, M. Chellali, S.M. Sheikholeslami, and J.C. Valenzuela-Tripodoro, Triple Roman domination in graphs, Applied Math. Comput. 391 (2021), Article ID: 125444.
[3] H. Abdollahzadeh Ahangar, J. Amjadi, M. Chellali, S. Nazari-Moghaddam, and S.M. Sheikholeslami, Total Roman reinforcement in graphs., Discuss. Mathe. Graph Theory 39 (2019), no. 4, 787–803.
[4] H. Abdollahzadeh Ahangar, M. Chellali, D. Kuziak, and V. Samodivkin, On maximal Roman domination in graphs, Int. J. Comput. Math. 93 (2016), no. 7, 1093–1102.
[5] H. Abdollahzadeh Ahangar, M. Chellali, S.M. Sheikholeslami, M. Soroudi, and L. Volkmann, Total vertex-edge domination in trees, Acta Math. Univ. Comenianae 90 (2021), no. 2, 127–143.
[6] R. Boutrig, M. Chellali, T.W. Haynes, and S.T. Hedetniemi, Vertex-edge domination in graphs, Aequationes Math. 90 (2016), no. 2, 355–366.
[7] A. Brandstädt, V.B. Le, and J.P. Spinrad, Graph classes: A survey, SIAM, Philadelphia, 2004.
[8] 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.
[9] B. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Information and Computation 85 (1990), no. 1, 12–75.
[10] M.R. Garey and D.S. Johnson, Computers and Interactability : A Guide to the Theory of NP-completeness, Freeman, New York, 1979.
[11] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker Inc. New York, 1998.
[12] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker Inc. New York,
1998.
[13] M.A. Henning and A. Pandey, Algorithmic aspects of semitotal domination in graphs, Theor. Comput. Sci. 766 (2019), 46–57.
[14] B. Krishnakumari, Y. B. Venkatakrishnan, and M. Krzywkowski, Bounds on the vertex–edge domination number of a tree, Comptes Rendus Mathematique 352 (2014), no. 5, 363–366.
[15] H.N. Kumar and Y.B. Venkata Krishna, Vertex-edge Roman domination in graphs, Kragujevac J. Math. 45 (2021), no. 5, 685–698.
[16] C.E. Leiserson, R.L. Rivest, T.H. Cormen, and C. Stein, Introduction to Algorithms, MIT press Cambridge, MA, 2001.
[17] J. Lewis, S.T. Hedetniemi, T.W. Haynes, and G.H. Fricke, Vertex-edge domination, Util. Math. 81 (2010), 193–213.
[18] J.R. Lewis, Vertex-Edge and Edge-Vertex Domination in Graphs, Ph.D. thesis, Clemson University, Clemson, 2007.
[19] M.-S. Lin and C.-M. Chen, Counting independent sets in tree convex bipartite graphs, Discrete Appl. Math. 218 (2017), 113–122.
[20] N. Mahadev and U. Peled, Threshold Graphs and Related Topics, Elsevier, 1995.
[21] A. Oganian and J. Domingo-Ferrer, On the complexity of optimal microaggregation for statistical disclosure control, Statistical Journal of the United Nations Economic Commission for Europe 18 (2001), no. 4, 345–353.
[22] B.S. Panda and A. Pandey, Algorithm and hardness results for outer-connected dominating set in graphs, J. Graph Algorithms Appl. 18 (2014), 493–513.
[23] B.S. Panda, A. Pandey, and S. Paul, Algorithmic aspects of b-disjunctive domination in graphs, J. Comb. Optim. 36 (2018), no. 2, 572–590.
[24] S. Paul and K. Ranjan, On vertex-edge and independent vertex-edge domination, International Conference on Combinatorial Optimization and Applications, Springer, 2019, pp. 437–448.
[25] K.W. Peters, Theoretical and Algorithmic Results on Domination and Connectivity, Ph.D. thesis, Clemson University, Clemson, 1986.
[26] E.N. Satheesh, Some Variations of Domination and Applications, Ph.D. thesis, Mahatma Gandhi University, 2014.
[27] R. Uehara and Y. Uno, Efficient algorithms for the longest path problem, International Symposium on Algorithms and Computation, Springer, 2004, pp. 871–883.
[28] D.B. West, Introduction to Graph Theory, Upper Saddle River: Prentice Hall, 2001.
[29] M. Yannakakis, Node-and edge-deletion NP-complete problems, Proceedings of the tenth annual ACM symposium on Theory of computing, 1978, pp. 253–264.
[30] R. Ziemann and P. Zyliński, ˙ Vertex-edge domination in cubic graphs, Discrete Math. 343 (2020), no. 11, Article ID: 112075.
Communications in Combinatorics and Optimization
Volume 8, Issue 1
March 2023
Pages 23-37

Files

Share

How to cite

Statistics