2020/02/05 by J. Pavan Kumar, Kumar, J. Pavan, P. Venkata Subba Reddy +1
Computer Science · #05C69 #68Q25 #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.CC #cs.DM #msc:05C69 #msc:68Q25
paper · pdf · doi:10.48550/arxiv.2002.02408
arXiv admin note: substantial text overlap with arXiv:2001.11250, arXiv:2002.00002
arxiv created 2020/02/05 · arxiv updated 2020/02/07
Let G(V,E) be a simple, undirected and connected graph. A dominating set S ⊆ V(G) is called a 2-secure dominating set (2-SDS) in G, if for every pair of distinct vertices u1,u2 ∈ V(G) there exists a pair of distinct vertices v1,v2 ∈ S such that v1 ∈ N[u1], v2 ∈ N[u2] and (S ∖ \v1,v2\) ∪ \u1,u2 \ is a dominating set in G. The 2-secure domination number denoted by γ2s(G), equals the minimum cardinality of a 2-SDS in G. Given a graph G and a positive integer k, the 2 -Secure Domination ( 2 -SDM) problem is to check whether G has a 2 -secure dominating set of size at most k. It is known that 2 -SDM is NP-complete for bipartite graphs. In this paper, we prove that the 2 -SDM problem is NP-complete for planar graphs and doubly chordal graphs, a subclass of chordal graphs. We strengthen the NP-complete result for bipartite graphs, by proving this problem is NP-complete for some subclasses of bipartite graphs namely, star convex bipartite, comb convex bipartite graphs. We prove that 2 -SDM is linear time solvable for bounded tree-width graphs. We also show that the 2 -SDM is W[2]-hard even for split graphs. The Minimum 2 -Secure Dominating Set (M2SDS) problem is to find a 2 -secure dominating set of minimum size in the input graph. We propose a Δ(G)+1 - approximation algorithm for M2SDS, where Δ(G) is the maximum degree of the input graph G and prove that M2SDS cannot be approximated within (1 - ε) ln(| V | ) for any ε> 0 unless NP ⊆ DTIME(| V | O(log log | V | )) . % even for bipartite graphs. A secure dominating set of a graph defends one attack at any vertex of the graph. Finally, we show that the M2SDS is APX-complete for graphs with Δ(G)=4.