Geodesic
On the Complexity of Reinforcement in Graphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 877-887

Voir la notice de l'article provenant de la source Library of Science

We show that the decision problem for p-reinforcement, p-total rein- forcement, total restrained reinforcement, and k-rainbow reinforcement are NP-hard for bipartite graphs.
Keywords: domination, total domination, total restrained domination, p- domination, k-rainbow domination, reinforcement, NP-hard 
Rad, Nader Jafari. On the Complexity of Reinforcement in Graphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 877-887. http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a8/
@article{DMGT_2016_36_4_a8,
     author = {Rad, Nader Jafari},
     title = {On the {Complexity} of {Reinforcement} in {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {877--887},
     year = {2016},
     volume = {36},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a8/}
}
TY  - JOUR
AU  - Rad, Nader Jafari
TI  - On the Complexity of Reinforcement in Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 877
EP  - 887
VL  - 36
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a8/
LA  - en
ID  - DMGT_2016_36_4_a8
ER  - 
%0 Journal Article
%A Rad, Nader Jafari
%T On the Complexity of Reinforcement in Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 877-887
%V 36
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a8/
%G en
%F DMGT_2016_36_4_a8

[1] M. Blidia, M. Chellali and L. Volkmann, Some bounds on the p-domination number in trees, Discrete Math. 306 (2006) 2031-2037. doi: 10.1016/j.disc.2006.04.010

[2] J.R.S. Blair, W. Goddard, S.T. Hedetniemi, S. Horton, P. Jones and G. Kubicki, On domination and reinforcement numbers in trees, Discrete Math. 308 (2008) 1165-1175. doi: 10.1016/j.disc.2007.03.067

[3] B. Brešar, M.A. Henning and D.F. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008) 213-225.

[4] B. Brešar an T.K. Šumenjak, On the 2-rainbow domination in graphs, Discrete Appl. Math. 155 (2007) 2394-2400. doi: 10.1016/j.dam.2007.07.018

[5] M. Chellali, O. Favaron, A. Hansberg and L. Volkmann, k-domination and k- independence in graphs: A survey, Graphs Combin. 28 (2012) 1-55. doi: 10.1007/s00373-011-1040-3

[6] X.-G. Chen, D-X. Ma and L. Sun, On total restrained domination in graphs, Czechoslovak Math. J. 55 (2005) 165-173. doi: 10.1007/s10587-005-0012-2

[7] J. Cyman and J. Raczek, On the total restrained domination number of a graph, Australas. J. Combin. 36 (2006) 91-100.

[8] G.S. Domke and R.C. Laskar, The bondage and reinforcement numbers of γf for some graphs, Discrete Math. 167/168 (1997) 249-259. doi: 10.1016/S0012-365X(97)00232-X

[9] J.E. Dunbar, T.W. Haynes, U. Teschner and L. Volkmann, Bondage, insensitivity, and reinforcement, in: T.W. Haynes, S.T. Hedetniemi and P.J. Slater (Ed(s)), Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998) 471-489.

[10] J.F. Fink and M.S. Jacobson, n-domination in graphs, in: Y. Alavi and A.J. Schwenk (Ed(s)), Graph Theory with Applications to Algorithms and Computer Science (Wiley, New York, 1985) 283-300.

[11] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).

[12] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).

[13] M.A. Henning, N. Jafari Rad and J. Raczek, A note on total reinforcement in graphs, Discrete Appl. Math. 159 (2011) 1443-1446. doi: 10.1016/j.dam.2011.04.024

[14] M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Verlag, New York, 2013).

[15] F.-T. Hu and M.Y. Sohn, The algorithmic complexity of bondage and reinforcement problems in bipartite graphs, Theoret. Comput. Sci. 535 (2014) 46-53. doi: 10.1016/j.tcs.2014.04.005.

[16] F.-T. Hu and J.-M. Xu, On the complexity of the bondage and reinforcement prob- lems, J. Complexity 28 (2012) 192-201. doi: 10.1016/j.jco.2011.11.001

[17] N. Jafari Rad and L. Volkmann, Total restrained reinforcement in graphs, AKCE Int. J. Graphs Comb. 13 (2016) 16-21. doi: 10.1016/j.akcej.1016.02.003

[18] J. Kok and C.M. Mynhardt, Reinforcement in graphs, Congr. Numer. 79 (1990) 225-231.

[19] Y. Lu, F.-T. Hu and J.-M. Xu, On the p-reinforcement and the complexity, J. Comb. Optim. 29 (2015) 389-405. doi: 10.1007/s10878-013-9597-9

[20] D. Rautenbach and L. Volkmann, New bounds on the k-domination number and the k-tuple domination number, Appl. Math. Lett. 20 (2007) 98-102. doi: 10.1016/j.aml.2006.03.006

[21] R.S. Shaheen, Bounds for the 2-domination number of toroidal grid graphs, Int. J. Comput. Math. 86 (2009) 584-588. doi: 10.1080/00207160701690284

[22] N. Sridharan, M.D. Elias and V.S.A. Subramanian, Total reinforcement number of a graph, AKCE Int. J. Graphs Combin. 4 (2007) 197-202.

[23] C. Tong, X. Lin, Y. Yang and M. Luo, 2-rainbow domination of generalized Petersen graphs P(n, 2), Discrete Appl. Math. 157 (2009) 1932-1937. doi: 10.1016/j.dam.2009.01.020

[24] Y. Wu and N. Jafari Rad, Bounds on the 2-rainbow domination number of graphs, Graphs Combin. 29 (2013) 1125-1133. doi: 10.1007/s00373-012-1158-y

[25] Y. Wu and H. Xing, Note on 2-rainbow domination and Roman domination in graphs, Appl. Math. Lett. 23 (2010) 706-709. doi: 10.1016/j.aml.2010.02.012

[26] G. Xu, 2-rainbow domination in generalized Petersen graphs P(n, 3), Discrete Appl. Math. 157 (2009) 2570-2573. doi: 10.1016/j.dam.2009.03.016

[27] J.H. Zhang, H.L. Liu and L. Sun, Independence bondage number and reinforcement number of some graphs, Trans. Beijing Inst. Tech. 23 (2003) 140-142.