Reconfiguring minimum dominating sets in trees

Magdalena Lemańska , Paweł Żyliński

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 dominatingsets ofa tree.
Author Magdalena Lemańska
Magdalena Lemańska,,
-
, Paweł Żyliński (FMPI / II)
Paweł Żyliński,,
- Institute of Informatics
Journal seriesJournal of Graph Algorithms and Applications, ISSN 1526-1719, (N/A 70 pkt)
Issue year2020
Vol24
No1
Pages47-61
Publication size in sheets0.7
ASJC Classification1700 General Computer Science; 1703 Computational Theory and Mathematics; 1706 Computer Science Applications; 2608 Geometry and Topology; 2614 Theoretical Computer Science
DOIDOI:10.7155/jgaa.00517
URL http://jgaa.info/accepted/2020/517.pdf
Languageen angielski
Score (nominal)70
Score sourcejournalList
ScoreMinisterial score = 70.0, 16-03-2020, ArticleFromJournal
Publication indicators Scopus SNIP (Source Normalised Impact per Paper): 2018 = 1.165
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?