On the distance-edge-monitoring numbers of graphs

Foucaud et al. (2022) recently introduced and initiated the study of a new graphtheoretic concept in the area of network monitoring. For a set M of vertices and an edge e of a graph G, let P(M, e) be the set of pairs (x, y) with a vertex x of M and a vertex y of V(G) such that d(G)(x, y) not equal d(G-e)(x, y). For a vertex x, let EM(x) be the set of edges e such that there exists a vertex v in G with (x, v) is an element of P({x}, e). A set M of vertices of a graph G is distance-edge-monitoring set if every edge e of G is monitored by some vertex of M, that is, the set P(M, e) is nonempty. The distance-edge-monitoring number of a graph G, denoted by dem(G), is defined as the smallest size of distance-edge-monitoring sets of G. In this paper, we continue the study of distance-edge-monitoring sets. In particular, we give upper and lower bounds of P(M, e), EM(x), dem(G), respectively, and extremal graphs attaining the bounds are characterized. We also characterize the graphs with dem(G) = 3. In addition, we give some properties of the graph G with dem(G) = n - 2. (c) 2023 Elsevier B.V. All rights reserved.