Perturbation results for distance-edge-monitoring numbers

• DOI: 10.48550/arxiv.2301.02507
• Publication Date: 2023-01-01
• Authors: Chenxu Yang; Ralf Klasing; Changxiang He; Yaping Mao
• Keywords: Bound graph

Foucaud et al. recently introduced and initiated the study of a new graph-theoretic concept in area network monitoring. Given graph $G=(V(G), E(G))$, set $M \subseteq V(G)$ is distance-edge-monitoring if for every edge $e \in E(G)$, there vertex $x M$ $y such that $e$ belongs to all shortest paths between $x$ $y$. The smallest size $G$ denoted by $\operatorname{dem}(G)$. Denoted $G-e$ (resp. $G \backslash u$) subgraph obtained removing from $u$ together with its incident edges $G$). In this paper, we first show $\operatorname{dem}(G-e)- \operatorname{dem}(G)\leq 2$ any E(G)$. Moreover, bound sharp. Next, construct two graphs $H$ $\operatorname{dem}(G)-\operatorname{dem}(G\setminus u)$ $\operatorname{dem}(H\setminus v)-\operatorname{dem}(H)$ can be arbitrarily large, where $u $v V(H)$. We also relation $\operatorname{dem}(H)$ $\operatorname{dem}(G)$, $G$. end, give an algorithm judge whether distance-edge monitoring still remain resulting when deleted.