A Note on the Paper “Eternal security in graphs” by Goddard, Hedetniemi, and Hedetniemi (2005)

Andrei Braga1, Cid C. de Souza1, Orlando Lee1
1Institute of Computing, State University of Campinas, 13083-852 Campinas, SP, Brazil

Abstract

In the paper “Eternal security in graphs” by Goddard, Hedetniemi and Hedetniemi (2005, [4]), the authors claimed that, for any Cayley graph, the eternal \(m\)-security number equals the minimum cardinality of a dominating set. However, the equality is false. In this note, we present a counterexample and comment on the eternal \(m\)-security number for Cayley graphs.