Geodesic
Reconfiguring Minimum Dominating Sets in Trees
Journal of Graph Algorithms and Applications, Tome 24 (2020) no. 1, pp. 47-61.

Voir la notice de l'article dans Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00517
Mots-clés : domination, tree, γ-graph, diameter 
@article{JGAA_2020_24_1_a2,
     author = {Magdalena Lema\'nska and Pawe{\l} \.Zyli\'nski},
     title = {Reconfiguring {Minimum} {Dominating} {Sets} in {Trees}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {47--61},
     publisher = {mathdoc},
     volume = {24},
     number = {1},
     year = {2020},
     doi = {10.7155/jgaa.00517},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/articles/10.7155/jgaa.00517/}
}
TY  - JOUR
AU  - Magdalena Lemańska
AU  - Paweł Żyliński
TI  - Reconfiguring Minimum Dominating Sets in Trees
JO  - Journal of Graph Algorithms and Applications
PY  - 2020
SP  - 47
EP  - 61
VL  - 24
IS  - 1
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/articles/10.7155/jgaa.00517/
DO  - 10.7155/jgaa.00517
LA  - en
ID  - JGAA_2020_24_1_a2
ER  - 
%0 Journal Article
%A Magdalena Lemańska
%A Paweł Żyliński
%T Reconfiguring Minimum Dominating Sets in Trees
%J Journal of Graph Algorithms and Applications
%D 2020
%P 47-61
%V 24
%N 1
%I mathdoc
%U https://geodesic-test.mathdoc.fr/articles/10.7155/jgaa.00517/
%R 10.7155/jgaa.00517
%G en
%F JGAA_2020_24_1_a2
Magdalena Lemańska; Paweł Żyliński. Reconfiguring Minimum Dominating Sets in Trees. Journal of Graph Algorithms and Applications, Tome 24 (2020) no. 1, pp. 47-61. doi : 10.7155/jgaa.00517. https://geodesic-test.mathdoc.fr/articles/10.7155/jgaa.00517/

Cité par Sources :