آمار
| تعداد نشریات | 5 |
| تعداد شماره‌ها | 116 |
| تعداد مقالات | 1,333 |
| تعداد مشاهده مقاله | 1,336,431 |
| تعداد دریافت فایل اصل مقاله | 1,268,840 |
Algorithmic complexity of three domination subdivision number problems in graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 05 اردیبهشت 1404 اصل مقاله (448.17 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2025.29896.2213 | ||
| نویسندگان | ||
| Deepak M. Bakal* ؛ Y.M. Borse؛ B.N. Waphare | ||
| Department of Mathematics, Savitribai Phule Pune University, Pune-411007, India | ||
| چکیده | ||
| 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 $\mathrm{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]. | ||
| کلیدواژه‌ها | ||
| Algorithmic Complexity؛ NP-hardness؛ Independent domination subdivision number؛ Total domination subdivision number؛ Paired domination subdivision number | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 318 تعداد دریافت فایل اصل مقاله: 109 |
||