Algorithmic complexity of secure connected domination in graphs
Let be a simple, undirected, and connected graph. A connected (total) dominating set is a secure connected (total) dominating set of G, if for each there exists such that and is a connected (total) dominating set of G. The minimum cardinality of a secure connected (total) dominating set of G denoted...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2020-09-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1016/j.akcej.2019.08.012 |
| _version_ | 1818391810972581888 |
|---|---|
| author | J. Pavan Kumar P. Venkata Subba Reddy S. Arumugam |
| author_facet | J. Pavan Kumar P. Venkata Subba Reddy S. Arumugam |
| author_sort | J. Pavan Kumar |
| collection | DOAJ |
| description | Let be a simple, undirected, and connected graph. A connected (total) dominating set is a secure connected (total) dominating set of G, if for each there exists such that and is a connected (total) dominating set of G. The minimum cardinality of a secure connected (total) dominating set of G denoted by 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. |
| first_indexed | 2024-12-14T05:19:27Z |
| format | Article |
| id | doaj.art-7963f805870f467aa0ef5e5001c68562 |
| institution | Directory Open Access Journal |
| issn | 0972-8600 2543-3474 |
| language | English |
| last_indexed | 2024-12-14T05:19:27Z |
| publishDate | 2020-09-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | AKCE International Journal of Graphs and Combinatorics |
| spelling | doaj.art-7963f805870f467aa0ef5e5001c685622022-12-21T23:15:43ZengTaylor & Francis GroupAKCE International Journal of Graphs and Combinatorics0972-86002543-34742020-09-011731010101310.1016/j.akcej.2019.08.0121740005Algorithmic complexity of secure connected domination in graphsJ. Pavan Kumar0P. Venkata Subba Reddy1S. Arumugam2Department of Computer Science and Engineering National Institute of Technology WarangalDepartment of Computer Science and Engineering National Institute of Technology WarangalKalasalingam Academy of Research and EducationLet be a simple, undirected, and connected graph. A connected (total) dominating set is a secure connected (total) dominating set of G, if for each there exists such that and is a connected (total) dominating set of G. The minimum cardinality of a secure connected (total) dominating set of G denoted by 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.http://dx.doi.org/10.1016/j.akcej.2019.08.012dominationsecure dominationsecure connected dominationw[2]-hard |
| spellingShingle | J. Pavan Kumar P. Venkata Subba Reddy S. Arumugam Algorithmic complexity of secure connected domination in graphs AKCE International Journal of Graphs and Combinatorics domination secure domination secure connected domination w[2]-hard |
| title | Algorithmic complexity of secure connected domination in graphs |
| title_full | Algorithmic complexity of secure connected domination in graphs |
| title_fullStr | Algorithmic complexity of secure connected domination in graphs |
| title_full_unstemmed | Algorithmic complexity of secure connected domination in graphs |
| title_short | Algorithmic complexity of secure connected domination in graphs |
| title_sort | algorithmic complexity of secure connected domination in graphs |
| topic | domination secure domination secure connected domination w[2]-hard |
| url | http://dx.doi.org/10.1016/j.akcej.2019.08.012 |
| work_keys_str_mv | AT jpavankumar algorithmiccomplexityofsecureconnecteddominationingraphs AT pvenkatasubbareddy algorithmiccomplexityofsecureconnecteddominationingraphs AT sarumugam algorithmiccomplexityofsecureconnecteddominationingraphs |