Complexity of the paired domination subdivision problem

Document Type : Original paper

Authors

1 Azarbaijan Shahid Madani University

2 University of Blida

Abstract

The paired domination subdivision number of a graph $G$ is the minimum number of edges that must be subdivided (where each edge in $G$ can be subdivided at most once) in order to increase the paired domination number of $G$. In this note, we show that the problem of computing the paired-domination subdivision number is NP-hard for bipartite graphs.

Keywords

Main Subjects

References

[1] W.J. Desormeaux, T.W. Haynes, and M.A. Henning, Paired-domination in graphs, Topics in Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer, 2020, pp. 31–77.
[2] Y. Egawa, M. Furuya, and M. Takatou, Upper bounds on the paired domination subdivision number of a graph, Graphs Combin. 29 (2013), no. 4, 843–856.
[3] O. Favaron, H. Karami, and S.M. Sheikholeslami, Paired-domination subdivision numbers of graphs, Graphs Combin. 25 (2009), no. 4, 503-512.
[4] G. Hao, S.M. Sheikholeslami, M. Chellali, R. Khoeilar, and H. Karami, On the paired-domination subdivision number of a graph, Mathematics 9 (2021), no. 4,  ID: 439.
[5] T.W. Haynes and P.J. Slater, Paired-domination in graphs, Networks 32 (1998), no. 3, 199–206.
[6] D.S. Johnson and M.R. Garey, Computers and intractability: A guide to the theory of NP-completeness, Freeman, San Francisco, 1979.
[7] X. Qiang, S. Kosari, Z. Shao, S.M. Sheikholeslami, M. Chellali, and H. Karami, A note on the paired-domination subdivision number of trees, Mathematics 9 (2021), no. 2,  ID:181.
[8] Z. Shao, S.M. Sheikholeslami, M. Chellali, R. Khoeilar, and H. Karami, A proof of a conjecture on the paired-domination subdivision number, (submitted). 
[9] S. Wei, G. Hao, S.M. Sheikholeslami, R. Khoeilar, and H. Karami, On the paireddomination subdivision number of trees, Mathematics 9 (2021), no. 10, ID: 1135.
Communications in Combinatorics and Optimization
Volume 7, Issue 2
December 2022
Pages 177-182

Files

Share

How to cite

Statistics