Contents

Eternal Security in Graphs of Fixed Independence Number

William F. Klostermeyer1, Gary MacGillivray2
1Dept. of Computer and Information Sciences University of North Florida Jacksonville, FL 32224-2669
2Dept. of Mathematics and Statistics University of Victoria Victoria, Canada

Abstract

We show that if the independence number of a graph is \( \alpha \), then the eternal security number of the graph is at most \( \binom{\alpha+1}{2} \), solving a problem stated by Goddard, Hedetniemi, and Hedetniemi \([JCMCC, \text{ vol. } 52, \text{ pp. } 160-180]\).