Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903429 | Electronic Notes in Discrete Mathematics | 2017 | 8 Pages |
Abstract
Let G=(V,E) be a simple, undirected and connected graph. A connected dominating set SâV(G) is a secure connected dominating set of G, if for each uâV(G)\S, there exists vâS such that (u,v)âE(G) and the set (S\{v})âª{u} is a connected dominating set of G. The minimum cardinality of a secure connected dominating set of G denoted γsc(G), is called the secure connected domination number of G. In this paper, we show that the decision problems of finding a minimum secure connected dominating set and a minimum secure total dominating set are NP-complete for split graphs. We initiate the study of 2-secure domination and show that the decision problem corresponding to the computation of 2-secure domination number of a graph is NP-complete, even when restricted to split graphs or bipartite graphs. Finally we show that given two positive integers k(â¥2) and n(â¥maxâ¡{4,k}) there exists a graph G with |V(G)|=n and γsc(G)=k.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Devendra Lad, P. Venkata Subba Reddy, J. Pavan Kumar,