Realizability problem of distance-edge-monitoring numbers

Let Gbe a graph with vertex set V(G) and edge set E(G). For a set Mof vertices and an edge eof a graph G, let P(M, e) be the set of pairs (x, y) with a vertex xof Mand a vertex yof V(G) such that dG(x, y) ≠dG−e(x, y). Given a vertex x, an edge eis said to be monitored by xif there exists a vertex vin Gsuch that (x, v) ∈P({x}, e), and the collection of such edges is EM(x). A set Mof vertices of a graph Gis distance-edge-monitoring (DEM for short) set if every edge eof Gis monitored by some vertex of M, that is, the set P(M, e) is nonempty. The DEM number dem(G) of a graph Gis defined as the smallest size of such a set in G. The vertices of Mrepresent distance probes in a network modeled by G; when the edge efails, the distance from xto yincreases, and thus we are able to detect the failure. In this paper, we first give some bounds or exact values of line graphs of trees, grids, complete bipartite graphs, and obtain the exact values of DEM numbers for some graphs and their line graphs, including the friendship and wheel graphs. Next, for each n, m> 1, we obtain that there exists a graph Gn,msuch that dem(Gn,m) = nand dem(L(Gn,m)) = 4 or 2n+ t, for each integer t≥0. In the end, the DEM number for the line graph of a small-world network (DURT) is given.