Complexity issues of perfect secure domination in graphs
Padamutham Chakradhar, P. Venkata Subba Reddy · RAIRO - Theoretical Informatics and Applications · 2021
Let G = ( V , E ) be a simple, undirected and connected graph. A dominating set S is called a secure dominating set if for each u ∈ V \ S , there exists v ∈ S such that ( u , v ) ∈ E and ( S \{ v }) ∪{ u } is a dominating set of G . If further the vertex v ∈ S is unique, then S is called a perfect secure dominating set (PSDS). The perfect secure domination number γ ps ( G ) is the minimum cardinality of a perfect secure dominating set of G . Given a graph G and a positive integer k , the perfect secure domination (PSDOM) problem is to check whether G has a PSDS of size at most k . In this paper, we prove that PSDOM problem is NP-complete for split graphs, star convex bipartite graphs, comb convex bipartite graphs, planar graphs and dually chordal graphs. We propose a linear time algorithm to solve the PSDOM problem in caterpillar trees and also show that this problem is linear time solvable for bounded tree-width graphs and threshold graphs, a subclass of split graphs. Finally, we show that the domination and perfect secure domination problems are not equivalent in computational complexity aspects.