Article ID Journal Published Year Pages File Type
4650692 Discrete Mathematics 2008 5 Pages PDF
Abstract

The eternal domination number of a graph is the number of guards needed at vertices of the graph to defend the graph against any sequence of attacks at vertices. We consider the model in which at most one guard can move per attack and a guard can move across at most one edge to defend an attack. We prove that there are graphs G   for which γ∞(G)⩾α(G)+12, where γ∞(G)γ∞(G) is the eternal domination number of G   and α(G)α(G) is the independence number of G. This matches the upper bound proved by Klostermeyer and MacGillivray.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,