Monitoring the edges of product networks using distances

Abstract

Foucaud {\it 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)\ne d_{G-e}(x,y)$ where $x\in M$ and $y\in V(G)$. $M$ is called a \emph{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 {\em distance-edge-monitoring number} of $G$, denoted by $\mathrm{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 \{m\mathrm{dem}(H),n\mathrm{dem}(G)\}\le \mathrm{dem}(G\square H)\le m\mathrm{dem}(H)+n\mathrm{dem}(G)-\mathrm{dem}(G)\mathrm{dem}(H)$, where $\square$ 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.

v2, 21 pages