آمار
| تعداد نشریات | 7 |
| تعداد شماره‌ها | 102 |
| تعداد مقالات | 1,139 |
| تعداد مشاهده مقاله | 1,048,477 |
| تعداد دریافت فایل اصل مقاله | 867,673 |
Complexity of the paired domination subdivision problem | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 15، دوره 7، شماره 2، اسفند 2022، صفحه 177-182 اصل مقاله (373.96 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2021.27010.1180 | ||
| نویسندگان | ||
| Jafar Amjadi* 1؛ Mustapha Chellali2 | ||
| 1Azarbaijan Shahid Madani University | ||
| 2University of Blida | ||
| چکیده | ||
| 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. | ||
| کلیدواژه‌ها | ||
| Paired dominating set؛ Paired domination number؛ Paired domination subdivision number | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 475 تعداد دریافت فایل اصل مقاله: 465 |
||