Realizability problem of distance-edge-monitoring numbers

¹ School of Computer, Qinghai Normal University, Xining, Qinghai 810008, P.R. China
² Academy of Plateau Science and Sustainability, and School of Mathematics and Statistis, Qinghai Normal University, Xining, Qinghai 810008, P.R. China
³ Department of Mathematics and Statistics, Oakland University, Rochester, MI 48309, USA
⁴ School of Mathematical Science & Institute of Mathematics, Nanjing Normal University, Nanjing 210023, P.R. China

^* Corresponding author: maoyaping@ymail.com

Received: 14 May 2023
Accepted: 10 March 2024

Abstract

Let G be a graph with vertex set V (G) and edge set E(G). For a set M of vertices and an edge e of a graph G, let P (M, e) be the set of pairs (x, y) with a vertex x of M and a vertex y of V (G) such that d_G(x, y) ≠ d_G−e(x, y). Given a vertex x, an edge e is said to be monitored by x if there exists a vertex v in G such that (x, v) ∈ P ({x}, e), and the collection of such edges is EM(x). A set M of vertices of a graph G is distance-edge-monitoring (DEM for short) set if every edge e of G is monitored by some vertex of M, that is, the set P (M, e) is nonempty. The DEM number dem(G) of a graph G is defined as the smallest size of such a set in G. The vertices of M represent distance probes in a network modeled by G; when the edge e fails, the distance from x to y increases, 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 G_n,m such that dem(G_n,m) = n and dem(L(G_n,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.