Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650692 | Discrete Mathematics | 2008 | 5 Pages |
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
John L. Goldwasser, William F. Klostermeyer,