Reconfiguring Minimum Dominating Sets in Trees

Magdalena Lemańska; Paweł Żyliński

doi:10.7155/jgaa.00517

Reconfiguring Minimum Dominating Sets in Trees

Abstrakt

We provide tight bounds on the diameter of γ-graphs, which are reconfiguration graphs of the minimum dominating sets of a graph G. In particular, we prove that for any tree T of order n ≥ 3, the diameter of its γ-graph is at most n/2 in the single vertex replacement adjacency model, whereas in the slide adjacency model, it is at most 2(n − 1)/3. Our proof is constructive, leading to a simple linear-time algorithm for determining the optimal sequence of “moves” between two minimum dominating sets of a tree.

Cytowania

0

CrossRef
0

Web of Science
0

Scopus

Autorzy (2)

Magdalena Lemańska dr inż.
Paweł Żyliński

Cytuj jako

Pełna treść

pobierz publikację

pobrano 58 razy

Wersja publikacji: Accepted albo Published Version
Licencja: Copyright (2020 Journal of Graph Algorithms and Applications)

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

Słowa kluczowe

GAMMA GRAPHS, DIAMETER

Informacje szczegółowe

Kategoria:: Publikacja w czasopiśmie
Typ:: artykuły w czasopismach
Opublikowano w:: Journal of Graph Algorithms and Applications nr 24, strony 47 - 61,
ISSN: 1526-1719
Język:: angielski
Rok wydania:: 2020
Opis bibliograficzny:: Lemańska M., Żyliński P.: Reconfiguring Minimum Dominating Sets in Trees// Journal of Graph Algorithms and Applications -Vol. 24,iss. 1 (2020), s.47-61
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.7155/jgaa.00517
Weryfikacja:: Politechnika Gdańska