Algorithmic complexity of three domination subdivision number problems in graphs

Articles in Press

Document Type : Original paper

Authors

Department of Mathematics, Savitribai Phule Pune University, Pune-411007, India

Abstract

The paired, total, and independent domination subdivision number of a graph G     is the minimum number of edges that must be subdivided, where each edge can be subdivided at most once, in order to increase the paired, total, and independent domination number, respectively. In this paper,     we prove that the corresponding decision problems for paired, total, and independent domination subdivision numbers are NP-hard, even when restricted to bipartite graphs. Additionally, we point out the error in the previous proof of NP-hardness of the paired domination subdivision problem by Amjadi and Chellali  in  "Complexity of the paired domination subdivision problem" [Commun. Comb. Optim. 7 (2022), No.2, 177–182].

Keywords

Main Subjects

References

[1] J. Amjadi and M. Chellali, Complexity of the paired domination subdivision problem, Commun. Comb. Optim. 7 (2022), no. 2, 177–182.  https://doi.org/10.22049/CCO.2021.27010.1180
[2] J. Amjadi, R. Khoeilar, M. Chellali, and Z. Shao, On the Roman domination subdivision number of a graph, J. Comb. Optim. 40 (2020), no. 2, 501–511. https://doi.org/10.1007/s10878-020-00597-x
[3] J. Amjadi and H. Sadeghi, Double Roman domination subdivision number in graphs, Asian-Eur. J. Math. 15 (2022), no. 7, Article ID: 2250125.  https://doi.org/10.1142/S179355712250125X
[4] J. Amjadi and H. Sadeghi, Triple Roman domination subdivision number in graphs, Comput. Sci. J. Moldova 88 (2022), no. 1, 109–130.
[5] A. Babikir, M. Dettlaff, M.A. Henning, and M. Lema´nska, Independent domination subdivision in graphs, Graphs Combin. 37 (2021), no. 3, 691–709.   https://doi.org/10.1007/s00373-020-02269-3
[6] D. Bauer, F. Harary, J. Nieminen, and C.L. Suffel, Domination alteration sets in  graphs, Discrete Math. 47 (1983), no. 2-3, 153–161.  https://doi.org/10.1016/0012-365X(83)90085-7
[7] M. Dettlaff, J. Raczek, and J. Topp, Domination subdivision and domination multisubdivision numbers of graphs, Discuss. Math. Graph Theory 39 (2019),  no. 4, 829–839.  https://doi.org/10.7151/dmgt.2103
[8] O. Favaron, H. Karami, and S.M. Sheikholeslami, Paired-domination subdivision  numbers of graphs, Graphs Combin. 25 (2009), no. 4, 503–512.  https://doi.org/10.1007/s00373-009-0835-6
[9] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., San Francisco, CA, 1979.
[10] K. Haghparast, J. Amjadi, M. Chellali, and S.M. Sheikholeslami, On [k]-Roman domination subdivision number of graphs, AKCE Int. J. Graphs Comb. 19 (2022), no. 3, 261–267.  https://doi.org/10.1080/09728600.2022.2134836
[11] T. Haynes, S. Hedetniemi, and S. Hedetniemi, Domination and independence subdivision numbers of graphs, Discuss. Math. Graph Theory 20 (2000), no. 2, 271–280.  https://doi.org/10.7151/dmgt.1126
[12] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Domination in Graphs: Core Concepts, 1st ed., Springer Monographs in Mathematics, Springer Nature Switzerland AG, Cham, Switzerland, 2023.
[13] T.W. Haynes, S.T. Hedetniemi, and L.C. van der Merwe, Total domination subdivision numbers, J. Combin. Math. Combin. Comput. 44 (2003), 115–128.
[14] J. Huang and J.M. Xu, Domination and total domination contraction numbers of graphs, Ars Combin. 94 (2010), 431–443.
[15] J. Kok and C. M. Mynhardt, Reinforcement in graphs, Congr. Numer. 79 (1990), 225–231.
[16] S. Velammal, Studies in graph theory: Covering, independence, domination and related topics, Ph.D. thesis, Manonmaniam Sundaranar University, Tirunelveli, India, 1997.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 25 April 2025

Files

Share

How to cite

Statistics