2020/02/12 by Jakkepalli Pavan Kumar, Kumar, Jakkepalli Pavan, P. Venkata Subba Reddy +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2002.05538
A dominating set S is an Isolate Dominating Set (IDS) if the induced subgraph G[S] has at least one isolated vertex. In this paper, we initiate the study of new domination parameter called, isolate secure domination. An isolate dominating set S⊆ V is an isolate secure dominating set (ISDS), if for each vertex u ∈ V ∖ S, there exists a neighboring vertex v of u in S such that (S ∖ \v\) ∪ \u\ is an IDS of G. The minimum cardinality of an ISDS of G is called as an isolate secure domination number, and is denoted by γ0s(G). Given a graph G=(V,E) and a positive integer k, the ISDM problem is to check whether G has an isolate secure dominating set of size at most k. We prove that ISDM is NP-complete even when restricted to bipartite graphs and split graphs. We also show that ISDM can be solved in linear time for graphs of bounded tree-width.