Perturbation results for distance-edge-monitoring numbers

Abstract

Foucaud et al. recently introduced and initiated the study of a new graph-theoretic concept in the area of network monitoring. Given a graph $G=(V(G),E(G))$, a set $M\subseteq V(G)$ is a distance-edge-monitoring set if for every edge $e\in E(G)$, there is a vertex $x\in M$ and a vertex $y\in V(G)$ such that the edge $e$ belongs to all shortest paths between $x$ and $y$. The smallest size of such a set in $G$ is denoted by $\mathrm{dem}(G)$. Denoted by $G-e$ (resp. $G\backslash u$) the subgraph of $G$ obtained by removing the edge $e$ from $G$ (resp. a vertex $u$ together with all its incident edges from $G$). In this paper, we first show that $\mathrm{dem}(G-e)-\mathrm{dem}(G)\le 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 $\mathrm{dem}(G)-\mathrm{dem}(G\setminus u)$ and $\mathrm{dem}(H\setminus v)-\mathrm{dem}(H)$ can be arbitrarily large, where $u\in V(G)$ and $v\in V(H)$. We also study the relation between $\mathrm{dem}(H)$ and $\mathrm{dem}(G)$, where $H$ is a subgraph of $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 the graph $G$ is deleted.