|
|
|
|
Complexity of the Paired Domination Subdivision Problem
|
|
|
|
|
|
|
|
نویسنده
|
Amjadi Jafar ,Chellali Mustapha
|
|
منبع
|
Communications In Combinatorics And Optimization - 2022 - دوره : 7 - شماره : 2 - صفحه:177 -182
|
|
|
|
|
چکیده
|
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 Domination ,Paired Domination Subdivision Number ,Complexity
|
|
آدرس
|
Azarbaijan Shahid Madani University, Department Of Mathematics, Iran, University Of Blida, Lamda-Ro Laboratory, Department Of Mathematics, Algeria
|
|
پست الکترونیکی
|
m_chellali@yahoo.com
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|