Reconfiguring minimum dominating sets in trees
Magdalena Lemańska , Paweł Żyliński
AbstractWe 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 dominatingsets ofa tree.
|Journal series||Journal of Graph Algorithms and Applications, ISSN 1526-1719, (N/A 70 pkt)|
|Publication size in sheets||0.7|
|ASJC Classification||; ; ; ;|
|Score||= 70.0, 16-03-2020, ArticleFromJournal|
|Publication indicators||: 2018 = 1.165|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.