Affiliations: [a] School of Computer, Qinghai Normal University, Xining, Qinghai 810008, China. [email protected]
| [b] Université de Bordeaux, Bordeaux INP, CNRS, LaBRI, UMR 5800, Talence, France. [email protected]
| [c] College of Science, University of Shanghai for Science and Technology, Shanghai 200093, China. [email protected]
| [d] Academy of Plateau Science and Sustainabilit and School of Mathematics and Statistics, Xining, Qinghai 810008, China. [email protected]
Correspondence:
[†]
Corresponding author: Université de Bordeaux, Bordeaux INP, CNRS, LaBRI, UMR 5800, Talence, France.
Note: [*] Supported by the National Science Foundation of China (Nos. 12061059, 12271362), the Qinghai Key Laboratory of Internet of Things Project (2017-ZJ-Y21), and by the ANR project TEMPOGRAL (ANR-22-CE48-0001).
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 ⊆ V(G) is a distance-edge-monitoring set if for every edge e ∈ E(G), there is a vertex x ∈ M and a vertex y ∈ 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 dem(G). Denoted by G – e (resp. G\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 dem(G – e) – dem(G) ≤ 2 for any graph G and edge e ∈ E(G). Moreover, the bound is sharp. Next, we construct two graphs G and H to show that dem(G) – dem(G\u) and dem(H \ v) – dem(H) can be arbitrarily large, where u ∈ V(G) and v ∈ V(H). We also study the relation between dem(H) and 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 a graph G is deleted.
Keywords: Distance, Perturbation result, Distance-edge-monitoring set
