arXiv RP 2019 | tags:[ combinatorial games cactus graphs ]

# On the m-eternal Domination Number of Cactus Graphs

with Jan Matyáš Křišťan and Tomáš VallaThis research is a followup to Bachelor’s Thesis of Jan Matyáš Křišťan (available only with sign-in) ↗.

## Abstract

Given a graph $G$, guards are placed on vertices of $G$. Then vertices are subject to an infinite sequence of attacks, so that each attack must be defended by a guard moving from a neighboring vertex. The $m$-eternal domination number is the minimum number of guards such that the graph can be defended indefinitely. In this paper we study the $m$-eternal domination number of cactus graphs, that is, graphs where each edge lies in at most two cycles, and we consider two variants of the $m$-eternal domination number: multiple guards may and may not occupy a single vertex. We provide a new upper bound for the $m$-eternal domination number of cactus graphs, and for a subclass of cactus graphs called opuntias, where each vertex lies in at most two cycles, we prove that these two numbers are equal. Moreover, we present a linear-time algorithm for computing them.