Trees with large m-eternal domination number

Michael A. Henning, William F. Klostermeyer

Research output: Contribution to journalArticlepeer-review

2 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 characterize the class of trees of order  n with maximum possible m-eternal domination number, which is ⌈[Formula Presented]⌉.

Original languageEnglish
Pages (from-to)79-85
Number of pages7
JournalDiscrete Applied Mathematics
Volume211
DOIs
Publication statusPublished - 1 Oct 2016

Keywords

  • Dominating set
  • Eternal dominating set
  • Independent set
  • Tree

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Trees with large m-eternal domination number'. Together they form a unique fingerprint.

Cite this