Monitoring the edges of a graph using distances with given girth

For a vertex set M and an edge uv of a graph G, if there exists a vertex x∈M such that dG(x,u)≠dG−uv(x,u) or dG(x,v)≠dG−uv(x,v), then uv is monitored by x. A vertex set M of the graph G is a distance-edge-monitoring set (DEM set, for short) if all edges e∈E(G) are monitored by some vertices of M. The distance-edge-monitoring number dem(G) of a graph G is defined as the minimum cardinality of a DEM set of G. In this paper, we prove that dem(G)≤n−⌊g(G)/2⌋ for a connected graph G, which is not a tree, of order n, where g(G) (g for short) is the length of a shortest cycle in G. Furthermore, the equality holds if and only if G is a cycle C4 or a complete graph Kn (n≥3). Let Gk,g be the class of connected graphs with DEM number k and girth g. For any G∈Gk,g, we have |V(G)|≥k+⌊g(G)/2⌋. Furthermore, the equality holds if and only if g(G)=3 and k=n−1 or g(G)=4 and k=2. In addition, there exists a graph G∈Gk,g such that |V(G)| can be arbitrarily large. We also give the relation between dem(G) and |V(G)| for g(G)≥5, that is, dem(G)≤2n/5. Finally, we suggest some bounds and related extremal graphs for |E(G)|, where G∈Gk,g.