A method for eternally dominating strong grids

Autor: Alizée Gagnon, Alexander Hassler, Jerry Huang, Aaron Krim-Yee, Fionn Mc Inerney, Andrés Zacarías, Ben Seamone, Virgélot Virgile

Publikováno v: Discrete Mathematics & Theoretical Computer Science, Vol vol. 22 no. 1, Iss Graph Theory (2020)

In the eternal domination game, an attacker attacks a vertex at each turn and a team of guards must move a guard to the attacked vertex to defend it. The guards may only move to adjacent vertices and no more than one guard may occupy a vertex. The go

Externí odkaz: https://doaj.org/article/6e70fde30a8f42f19522d3f358164e73

A dynamic domination problem in trees

Autor: William Klostermeyer, Christina Mynhardt

Publikováno v: Transactions on Combinatorics, Vol 4, Iss 4, Pp 15-31 (2015)

We consider a dynamic domination problem for graphs in which an infinite sequence of attacks occur at vertices with guards and the guard at the attacked vertex is required to vacate the vertex by moving to a neighboring vertex with no guard. Other gu

Externí odkaz: https://doaj.org/article/5559404b7b8d4e8ca6eb770447ef4802

Eternal Domination: D-Dimensional Cartesian and Strong Grids and Everything in Between

Autor: Stéphane Pérennes, Fionn Mc Inerney, Nicolas Nisse

Publikováno v: Algorithmica
Algorithmica, Springer Verlag, 2021, 83 (5), pp.1459-1492
Algorithmica, 2021, 83 (5), pp.1459-1492. ⟨10.1007/s00453-020-00790-8⟩
Algorithmica, Springer Verlag, 2021, 83 (5), pp.1459-1492. ⟨10.1007/s00453-020-00790-8⟩

In the eternal domination game played on graphs, an attacker attacks a vertex at each turn and a team of guards must move a guard to the attacked vertex to defend it. The guards may only move to adjacent vertices on their turn. The goal is to determi

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::13e3507391221f2177aa1500e846dca1
https://doi.org/10.1007/s00453-020-00790-8

On eternal domination and Vizing-type inequalities

Autor: William F. Klostermeyer, Patrick Taylor, Elliot Krop, Colton Magnant, Keith Driscoll

Publikováno v: AKCE International Journal of Graphs and Combinatorics, Vol 17, Iss 3, Pp 708-712 (2020)

We show sharp Vizing-type inequalities for eternal domination. Namely, we prove that for any graphs G and H, where is the eternal domination function, α is the independence number, and is the strong product of graphs. This addresses a question of Kl

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7b2391a7890356502424dfc3077de872
https://doi.org/10.1016/j.akcej.2019.12.013

Graph domination and reconfiguration problems

Autor: Joffard, Alice

Publikováno v: Data Structures and Algorithms [cs.DS]. Université de Lyon, 2020. English. ⟨NNT : 2020LYSE1216⟩

This object of this thesis is to study graph domination and reconfiguration problems. A dominating set of a graph is a subset of vertices such that every vertex of the graph either is in the set, or is a neighbor of at least one vertex in the set. As

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::250b591a9f0535921ef7a650bcb13799
https://tel.archives-ouvertes.fr/tel-03419113/file/TH2020JOFFARDALICE.pdf