2021/12/06 by William F. Klostermeyer, Klostermeyer, William F., Gary MacGillivray +1
Computer Science · #Advanced Graph Theory Research #Optimization and Search Problems #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2112.03107
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). More than one guard is allowed to move in response to an attack. The m-eternal domination number is the minimum number of guards needed to defend the graph. We characterize the trees achieving several upper and lower bounds on the m-eternal domination number.