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

Wyszukiwarka

Domination subdivision and domination multisubdivision numbers of graphs

Abstrakt

The domination subdivision number sd(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 domination number of G. It has been shown [10] that sd(T)<=3 for any tree T. We prove that the decision problem of the domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the domination multisubdivision number of a nonempty graph G as a minimum positive integer k such that there exists an edge which must be subdivided k times to increase the domination number of G. We show that msd(G)<=3 for any graph G. The domination subdivision number and the domination multisubdivision number of a graph are incomparable in general, but we show that for trees these two parameters are equal. We also determine the domination multisubdivision number for some classes of graphs.

Cytowania

  • 5

    CrossRef

  • 0

    Web of Science

  • 6

    Scopus

Cytuj jako

Słowa kluczowe

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:
Discussiones Mathematicae Graph Theory strony 829 - 839,
ISSN: 1234-3099
Język:
angielski
Rok wydania:
2019
Opis bibliograficzny:
Dettlaff M., Raczek J., Topp J.: Domination subdivision and domination multisubdivision numbers of graphs// Discussiones Mathematicae Graph Theory. -, iss. 39 (2019), s.829-839
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.7151/dmgt.2103
Weryfikacja:
Politechnika Gdańska

wyświetlono 175 razy

Publikacje, które mogą cię zainteresować

Meta Tagi