The paired domination subdivision number sdpr(G) of a graph G is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the paired domination number of G. We prove that the decision problem of the paired domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the paired domination muttisubdivision number of a nonempty graph G, denoted by msdpr(Cr), as the minimum positive integer k such that there exists an edge which must be subdivided k times to increase the paired domination number of G. We show that msdpr(Gr) < 4 for any graph G with at least one edge. We also determine paired domination multisubdivision numbers for some classes of graphs. Moreover, we give a constructive characterizations of all trees with paired domination multisubdivision number equal to 4.
Authors
Additional information
- Category
- Publikacja w czasopiśmie
- Type
- artykuły w czasopismach
- Language
- angielski
- Publication year
- 2020
