Perturbation results for distance-edge-monitoring numbers
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915920709943296 |
|---|---|
| author | Yang, Chenxu Klasing, Ralf He, Changxiang Mao, Yaping |
| author_facet | Yang, Chenxu Klasing, Ralf He, Changxiang Mao, Yaping |
| contents | 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 $\operatorname{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 $\operatorname{dem}(G-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\setminus u)$ and $\operatorname{dem}(H\setminus v)-\operatorname{dem}(H)$ can be arbitrarily large, where $u \in V(G)$ and $v \in V(H)$. We also study the relation between $\operatorname{dem}(H)$ and $\operatorname{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_02507 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Perturbation results for distance-edge-monitoring numbers Yang, Chenxu Klasing, Ralf He, Changxiang Mao, Yaping Discrete Mathematics Data Structures and Algorithms Combinatorics 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 $\operatorname{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 $\operatorname{dem}(G-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\setminus u)$ and $\operatorname{dem}(H\setminus v)-\operatorname{dem}(H)$ can be arbitrarily large, where $u \in V(G)$ and $v \in V(H)$. We also study the relation between $\operatorname{dem}(H)$ and $\operatorname{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. |
| title | Perturbation results for distance-edge-monitoring numbers |
| topic | Discrete Mathematics Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2301.02507 |