Paired domination subdivision and multisubdivision numbers of graphs - Publikacja - MOST Wiedzy

Wyszukiwarka

Paired domination subdivision and multisubdivision numbers of graphs

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ść

pobierz publikację
pobrano 47 razy
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 107 razy

Publikacje, które mogą cię zainteresować

Meta Tagi