Monitoring the edges of a graph using distances with given girth

Chenxu Yang, Gang Yang, Sun Yuan Hsieh, Yaping Mao, Ralf Klasing

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Article number103528
JournalJournal of Computer and System Sciences
Volume143
DOIs
Publication statusPublished - 2024 Aug

All Science Journal Classification (ASJC) codes

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

Fingerprint

Dive into the research topics of 'Monitoring the edges of a graph using distances with given girth'. Together they form a unique fingerprint.

Cite this