2025/12/30 by Swathi D, N Sadagopan · 1 voice
Computer Science · #cs.DM
arxiv published 2025/12/30 · arxiv updated 2026/05/22
A dominating set S of a graph G(V,E) is called a secure dominating set if each vertex u ∈ V(G) ∖ S is adjacent to a vertex v ∈ S such that (S ∖ \v\) ∪ \u\ is a dominating set of G. The secure domination number γs(G) of G is the minimum cardinality of a secure dominating set of G. The Minimum Secure Domination problem is to find a secure dominating set of a graph G of cardinality γs(G). In this paper, the computational complexity of the secure domination problem on several graph classes is investigated. The decision version of secure domination problem was shown to be NP-complete on star(comb) convex split graphs and bisplit graphs. So we further focus on complexity analysis of secure domination problem under additional structural restrictions on bisplit graphs. In particular, by imposing chordality as a parameter, we analyse its impact on the computational status of the problem on bisplit graphs. We establish the P versus NP-C dichotomy status of secure domination problem under restrictions on cycle length within bisplit graphs. In addition, we establish that the problem is polynomial-time solvable in chain graphs. We also prove that the secure domination problem cannot be approximated for a bisplit graph within a factor of (1-ε)~ln~|V| for any ε> 0, unless NP ⊆ DTIME(|V|O(log~log~|V|)).