Complexity Issues of Perfect Secure Domination in Graphs
RAIRO. Theoretical Informatics and Applications, Tome 55 (2021), article no. 11

Let G = (V, E) be a simple, undirected and connected graph. A dominating set S is called a secure dominating set if for each u ∈ V \ S, there exists v ∈ S such that (u, v) ∈ E and (S \{v}) ∪{u} is a dominating set of G. If further the vertex v ∈ S is unique, then S is called a perfect secure dominating set (PSDS). The perfect secure domination number γ$$(G) is the minimum cardinality of a perfect secure dominating set of G. Given a graph G and a positive integer k, the perfect secure domination (PSDOM) problem is to check whether G has a PSDS of size at most k. In this paper, we prove that PSDOM problem is NP-complete for split graphs, star convex bipartite graphs, comb convex bipartite graphs, planar graphs and dually chordal graphs. We propose a linear time algorithm to solve the PSDOM problem in caterpillar trees and also show that this problem is linear time solvable for bounded tree-width graphs and threshold graphs, a subclass of split graphs. Finally, we show that the domination and perfect secure domination problems are not equivalent in computational complexity aspects.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ita/2021012
Classification : 05C69, 68Q25
Keywords: Secure domination, Perfect secure domination, NP-complete 
@article{ITA_2021__55_1_A13_0,
     author = {Chakradhar, P. and Venkata Subba Reddy, P.},
     title = {Complexity {Issues} of {Perfect} {Secure} {Domination} in {Graphs}},
     journal = {RAIRO. Theoretical Informatics and Applications},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ita/2021012},
     mrnumber = {4331904},
     zbl = {1483.05115},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2021012/}
}
TY  - JOUR
AU  - Chakradhar, P.
AU  - Venkata Subba Reddy, P.
TI  - Complexity Issues of Perfect Secure Domination in Graphs
JO  - RAIRO. Theoretical Informatics and Applications
PY  - 2021
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2021012/
DO  - 10.1051/ita/2021012
LA  - en
ID  - ITA_2021__55_1_A13_0
ER  - 
%0 Journal Article
%A Chakradhar, P.
%A Venkata Subba Reddy, P.
%T Complexity Issues of Perfect Secure Domination in Graphs
%J RAIRO. Theoretical Informatics and Applications
%D 2021
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ita/2021012/
%R 10.1051/ita/2021012
%G en
%F ITA_2021__55_1_A13_0
Chakradhar, P.; Venkata Subba Reddy, P. Complexity Issues of Perfect Secure Domination in Graphs. RAIRO. Theoretical Informatics and Applications, Tome 55 (2021), article no. 11. doi: 10.1051/ita/2021012

[1] A. Brandstädt, V. D. Chepoi and F. F. Dragan, The algorithmic use of hypertree structure and maximum neighbourhood orderings. Discrete Appl. Math. 82 (1995) 43–77. | MR | Zbl | DOI

[2] E. J. Cockayne, P. J. P. Grobler, W. R. Grundlingh, J. Munganga and J. H. Van Vuuren, Protection of a graph. Util. Math. 67 (2005) 19–32. | MR | Zbl

[3] B. Chaluvaraju, M. Chellali and K. A. Vidya, Perfect k-domination in graphs. Austr. J. Comb. 48 (2010) 175–184. | MR | Zbl

[4] B. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85 (1990) 12–75. | MR | Zbl | DOI

[5] F. F. Dragan, K. F. Prisakar and V. D. Chepoi, Location problems in graphs and the Helly property (in Russian). Diskr. Mat. 4 (1992) 67–73. | MR | Zbl

[6] M. R. Garey and D. S. Johnson, Computers and Interactability: A Guide to the Theory of NP-completeness. Freeman, New York (1979). | MR | Zbl

[7] T. W. Haynes, S. Hedetniemi and P. Slater, Domination in graphs: advanced topics. Marcel Dekker (1997). | MR | Zbl

[8] M. A. Henning and A. Pandey, Algorithmic aspects of semitotal domination in graphs. Theor. Comput. Sci. 766 (2019) 46–57. | MR | Zbl | DOI

[9] W. F. Klostermeyer and C. M. Mynhardt, Secure domination and secure total domination in graphs. Discuss. Math. Graph Theory. 28 (2008) 267–284. | MR | Zbl | DOI

[10] M. Lin and C. Chen, Counting independent sets in tree convex bipartite graphs. Discr. Appl. Math. 218 (2017) 113–122. | MR | Zbl | DOI

[11] N. Mahadev and U. Peled, Threshold Graphs and Related Topics. Elsevier (1995). | MR | Zbl

[12] H. B. Merouane and M. Chellali, On secure domination in graphs. Inf. Process. Lett. 115 (2015) 786–790. | MR | Zbl | DOI

[13] C. M. Mynhardt, H. C. Swart and L. Ungerer, Excellent trees and secure domination. Util. Math. 67 (2005) 255–267. | MR | Zbl

[14] A. Oganian and D. Josep, On the complexity of optimal microaggregation for statistical disclosure control. Stat. J. United Nations Economic Commission for Europe 18 (2001) 345–353. | DOI

[15] B. S. Panda and A. Pandey, Algorithm and hardness results for outer-connected dominating set in graphs. J. Graph Algor. Appl. 18 (2014) 493–513. | MR | Zbl | DOI

[16] S. V. D. Rashmi, S. Arumugam, K. R. Bhutani and P. Gartland, Perfect secure domination in graphs. Categ. General Algebr. Struct. Appl. 7 (2017) 125–140. | MR | Zbl

[17] P. M. Weichsel, Dominating sets in n-cubes. J. Graph Theory 18 (1994) 479–488. | MR | Zbl | DOI

[18] D. B. West, Introduction to Graph Theory. Prentice Hall, Upper Saddle River (2001). | MR | Zbl

Cité par Sources :