Double vertex-edge domination in graphs: complexity and algorithms
- PDF / 575,086 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 5 Downloads / 230 Views
Double vertex-edge domination in graphs: complexity and algorithms H. Naresh Kumar1 · D. Pradhan2 · Y. B. Venkatakrishnan1 Received: 12 July 2020 / Revised: 26 August 2020 / Accepted: 29 August 2020 © Korean Society for Informatics and Computational Applied Mathematics 2020
Abstract In a graph G = (V , E), a vertex v ∈ V is said to ve-dominate the edges incident on v as well as the edges adjacent to these incident edges on v. A set D ⊆ V is called a double vertex-edge dominating set if every edge of the graph is ve-dominated by at least two vertices of D. Given a graph G, the double vertex-edge dominating problem, namely Min-DVEDS is to find a minimum double vertex-edge dominating set of G. In this paper, we show that the decision version of Min-DVEDS is NP-complete for chordal graphs. We present a linear time algorithm to find a minimum double vertexedge dominating set in proper interval graphs. We also show that for a graph having n vertices, Min-DVEDS cannot be approximated within (1 − ε) ln n for any ε > 0 unless NP⊆ DTIME(n O(log log n) ). On positive side, we show that Min-DVEDS can be approximated by a factor of O(ln Δ). Finally, we show that Min-DVEDS is APXcomplete for graphs with maximum degree 5. Keywords Domination · Vertex-edge domination · Double vertex-edge domination · Polynomial time algorithm · NP-complete Mathematics Subject Classification 05C69 · 68Q25
A short version of this paper has been presented in WALCOM 2019.
B
Y. B. Venkatakrishnan [email protected] H. Naresh Kumar [email protected] D. Pradhan [email protected]
1
Department of Mathematics, SASTRA Deemed University, Thanjavur, India
2
Department of Mathematics and Computing, Indian Institute of Technology (ISM), Dhanbad, India
123
H. Naresh Kumar et al.
1 Introduction Let G = (V , E) be a simple and undirected graph. The sets N G (v) = {u ∈ V : uv ∈ E} and N G [v] = N G (v) ∪ {v} denote the open neighborhood and the closed neighborhood of a vertex v in G, respectively. A set D ⊆ V of a graph G = (V , E) is a dominating set of G if every vertex in V \ D is adjacent to some vertex in D. The domination number of a graph G, denoted by γ (G), is the minimum cardinality of a dominating set of G. Based on the utility in real life situations, variants of dominating set are introduced. Domination and its variants are extensively used in practical problems arising in facility location problems, in monitoring communication or electrical networks, problems in computer networking and in land surveying. For more details on domination and its variants, readers may refer to [7,8]. In the theory of domination in graphs, a set of vertices dominate another set of vertices or a set of edges dominate another set of edges. Peters [20] defined new type of domination, called vertex-edge domination, where a set of vertices dominates the edges of the graph. A vertex v vertex-edge dominates (abbreviated ve-dominates) edges incident with v as well as the edges incident with these incident edges. A subset S ⊆ V is a vertex-edge dominat
Data Loading...
