Eternal m-security subdivision numbers in graphs

Abstract

An eternal $m$-secure set of a graph $G = (V,E)$ is aset $S_0subseteq V$ that can defend against any sequence ofsingle-vertex attacks by means of multiple-guard shifts along theedges of $G$. A suitable placement of the guards is called aneternal $m$-secure set. The eternal $m$-security number$sigma_m(G)$ is the minimum cardinality among all eternal$m$-secure sets in $G$. An edge $uvin E(G)$ is subdivided if wedelete the edge $uv$ from $G$ and add a new vertex $x$ and twoedges $ux$ and $vx$. The eternal $m$-security subdivision number${rm sd}_{sigma_m}(G)$ of a graph $G$ is the minimum cardinalityof a set of edges that must be subdivided (where each edge in $G$can be subdivided at most once) in order to increase the eternal$m$-security number of $G$. In this paper, we study the eternal$m$-security subdivision number in trees. In particular, we showthat the eternal $m$-security subdivision number of trees is atmost 2 and we characterize all trees attaining this bound.