Reconfiguring Minimum Dominating Sets in Trees

Magdalena Lemańska; Paweł Żyliński

doi:10.7155/jgaa.00517

Reconfiguring Minimum Dominating Sets in Trees

Abstract

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.

Citations

0

CrossRef
0

Web of Science
0

Scopus

Authors (2)

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

Cite as

Full text

download paper

downloaded 60 times

Publication version: Accepted or Published Version
License: Copyright (2020 Journal of Graph Algorithms and Applications)

full content of the article see on external site open in new tab

Keywords

GAMMA GRAPHS, DIAMETER

Details

Category:: Articles
Type:: artykuły w czasopismach
Published in:: Journal of Graph Algorithms and Applications no. 24, pages 47 - 61,
ISSN: 1526-1719
Language:: English
Publication year:: 2020
Bibliographic description:: 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:: Digital Object Identifier (open in new tab) 10.7155/jgaa.00517
Verified by:: Gdańsk University of Technology