Perturbation results for distance-edge-monitoring numbers

Foucaud et al. recently introduced and initiated the study of a new graph-theoretic concept in the area of network monitoring. Let $G=(V, E)$ be a graph. A set of vertices $M \subseteq V(G)$ is a distance-edge-monitoring set of $G$ if any edges in $G$ can be monitored by a vertex in $M$. The distance-edge-monitoring number $\operatorname{dem}(G)$ is the minimum cardinality of a distance-edge-monitoring set of $G$. In this paper, we first show that $\operatorname{dem}(G\setminus e)- \operatorname{dem}(G)\leq 2$ for any graph $G$ and edge $e \in E(G)$. Moreover, the bound is sharp. Next, we construct two graphs $G$ and $H$ to show that $\operatorname{dem}(G)-\operatorname{dem}(G-u)$ and $\operatorname{dem}(H-v)-\operatorname{dem}(H)$ can be arbitrarily large, where $u \in V(G)$ and $v \in V(H)$. We also study the relationship between $\operatorname{dem}(H)$ and $\operatorname{dem}(G)$ for $H\subset G$. In the end, we give an algorithm to judge whether the distance-edge-monitoring set still remain in the resulting graph when any edge of a graph $G$ is deleted.