Search
Abstract
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 (2)
Cite as
Full text
- Publication version
- Accepted or Published Version
- License
- Copyright (2020 Charles Babbage Research Centre)
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach
- Published in:
-
Journal of Combinatorial Mathematics and Combinatorial Computing
no. 113,
pages 197 - 212,
ISSN: 0835-3026 - Language:
- English
- Publication year:
- 2020
- Bibliographic description:
- Raczek J., Dettlaff M.: Paired domination subdivision and multisubdivision numbers of graphs// Journal of Combinatorial Mathematics and Combinatorial Computing -, (2020), s.197-212
- Verified by:
- Gdańsk University of Technology
seen 106 times
Recommended for you
TOTAL DOMINATION MULTISUBDIVISION NUMBER OF A GRAPH
- D. Avella-alaminos,
- M. Dettlaff,
- M. Lemańska
- + 1 authors