Monitoring the edges of product networks using distances
share
Foucaud et al. recently introduced and initiated the study of a new graph-theoretic concept in the area of network monitoring. Let G be a graph with vertex set V(G), M a subset of V(G), and e be an edge in E(G), and let P(M, e) be the set of pairs (x,y) such that d_G(x, y)≠ d_G-e(x, y) where x∈ M and y∈ V(G). M is called a distance-edge-monitoring set if every edge e of G is monitored by some vertex of M, that is, the set P(M, e) is nonempty. The distance-edge-monitoring number of G, denoted by dem(G), is defined as the smallest size of distance-edge-monitoring sets of G. For two graphs G,H of order m,n, respectively, in this paper we prove that max{mdem(H),ndem(G)}≤dem(G H) ≤ mdem(H)+ndem(G) -dem(G)dem(H), where is the Cartesian product operation. Moreover, we characterize the graphs attaining the upper and lower bounds and show their applications on some known networks. We also obtain the distance-edge-monitoring numbers of join, corona, cluster, and some specific networks.
READ FULL TEXT