Monitoring the edges of a graph using distances with given girth
Chenxu Yang, Gang Yang, Sun‐Yuan Hsieh, Yaping Mao, Ralf Klasing
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 ) ≤ 2 n / 5 for g ( G ) ≥ 5 .