## Abstract

A set M of vertices of a graph G is a distance-edge-monitoring set if for every edge e∈G, there is a vertex x∈M and a vertex y∈G such that e belongs to all shortest paths between x and y. We denote by dem(G) the smallest size of such a set in G. In this paper, we prove that dem(G)≤n−⌊g(G)/2⌋ for any connected graph G, which is not a tree, of order n, where g(G) is the length of a shortest cycle in G, and give the graphs with dem(G)=n−⌊g(G)/2⌋. We also obtain that |V(G)|≥k+⌊g(G)/2⌋ for every connected graph G with dem(G)=k and g(G)=g. Furthermore, the lower bound holds if and only if g=3 and k=n−1 or g=4 and k=2. We prove that dem(G)≤2n/5 for g(G)≥5.

Original language | English |
---|---|

Article number | 103528 |

Journal | Journal of Computer and System Sciences |

Volume | 143 |

DOIs | |

Publication status | Published - 2024 Aug |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- General Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics