Portal de Periódicos da CAPES

Graphs with equal eternal vertex cover and eternal domination numbers

2011; Elsevier BV; Volume: 311; Issue: 14 Linguagem: Inglês

10.1016/j.disc.2011.03.026

1872-681X

William F. Klostermeyer, Christina M. Mynhardt,

Complexity and Algorithms in Graphs

Mobile guards on the vertices of a graph are used to defend it against an infinite sequence of attacks on either its vertices or its edges. If attacks occur at vertices, this is known at the eternal domination problem. If attacks occur at edges, this is known as the eternal vertex cover problem. We focus on the model in which all guards can move to neighboring vertices in response to an attack. Motivated by the question of which graphs have equal eternal vertex cover and eternal domination numbers, a number of results are presented; one of the main results of the paper is that the eternal vertex cover number is greater than the eternal domination number (in the all-guards move model) in all graphs of minimum degree at least two.