Wyszukiwarka
Abstrakt
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.
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- Licencja
- Copyright (2020 Charles Babbage Research Centre)
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach
- Opublikowano w:
-
Journal of Combinatorial Mathematics and Combinatorial Computing
nr 113,
strony 197 - 212,
ISSN: 0835-3026 - Język:
- angielski
- Rok wydania:
- 2020
- Opis bibliograficzny:
- Raczek J., Dettlaff M.: Paired domination subdivision and multisubdivision numbers of graphs// Journal of Combinatorial Mathematics and Combinatorial Computing -, (2020), s.197-212
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 106 razy
Publikacje, które mogą cię zainteresować
TOTAL DOMINATION MULTISUBDIVISION NUMBER OF A GRAPH
- D. Avella-alaminos,
- M. Dettlaff,
- M. Lemańska
- + 1 autorów