Bounds for the m-eternal domination number of a graph

Michael A. Henning, William F. Klostermeyer, Gary Macgillivray

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

Mobile guards on the vertices of a graph are used to defend the graph against an infinite sequence of attacks on vertices. A guard must move from a neighboring vertex to an attacked vertex (we assume attacks happen only at vertices containing no guard and that each vertex contains at most one guard). More than one guard is allowed to move in response to an attack. The m-eternal domination number, γm(G), of a graph G is the minimum number of guards needed to defend G against any such sequence. We show that if G is a connected graph with minimum degree at least 2 and of order n ≥ 5, then γm(G) ≤ (n − 1)/2, and this bound is tight. We also prove that if G is a cubic bipartite graph of order n, then γm(G) ≤ 7n/16.

Original languageEnglish
Pages (from-to)91-103
Number of pages13
JournalContributions to Discrete Mathematics
Volume12
Issue number2
Publication statusPublished - 2017

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Bounds for the m-eternal domination number of a graph'. Together they form a unique fingerprint.

Cite this