Algorithmic complexity of secure connected domination in graphs. Issue 3 (1st September 2020)

• Record Type: Journal Article
• Authors: Kumar, J. Pavan; Reddy, P. Venkata Subba; Arumugam, S.
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 17:Issue 3(2020)
• Page Start: 1010
• Page End: 1013
• Publication Date: 2020-09-01
• Subjects: Domination -- secure domination -- secure connected domination -- w[2]-hard
• DOI: 10.1016/j.akcej.2019.08.012
• Languages: English
• ISSNs: 0972-8600

Abstract

Abstract: 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 u v ∈ E and ( S ∖ { v } ) ∪ { u } is a connected (total) dominating set of G. The minimum cardinality of a secure connected (total) dominating set of G denoted by γ s c ( G ) ( γ s t ( 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.