2020/02/03 by Jakkepalli Pavan Kumar, Kumar, Jakkepalli Pavan, P. Venkata Subba Reddy +3
Computer Science · #05C69 #68Q25 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2002.00713
openalex publication_date 2020/02/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G = (V,E) be a simple, undirected and connected graph. A connected (total) dominating set S ⊆ V is a secure connected (total) dominating set of G, if for each u ∈ V ∖ S, there exists v ∈ S such that uv ∈ E and (S ∖ \lbrace v \rbrace) ∪ \lbrace u \rbrace is a connected (total) dominating set of G. The minimum cardinality of a secure connected (total) dominating set of G denoted by γsc (G) (γst(G)), is called the secure connected (total) domination number of G. In this paper, we show that the decision problems corresponding to secure connected domination number and secure total domination number are NP-complete even when restricted to split graphs or bipartite graphs. The NP-complete reductions also show that these problems are w[2]-hard. We also prove that the secure connected domination problem is linear time solvable in block graphs and threshold graphs.