论文标题
图形的距离边缘监测数
On the distance-edge-monitoring numbers of graphs
论文作者
论文摘要
Foucaud等。 [离散应用。数学。 319（2022），424-438]最近引入并启动了对网络监控领域的新图理论概念的研究。对于$ m $的顶点和图形$ g $的边缘$ e $，让$ p（m，e）$是一组对$（x，y）$，带有顶点$ x $ $ $ m $ $ m $和一个顶点$ y $ y $ y $ v（g）$，例如$ d_g（x，x，x，x，x，x，yq d_ neq d_ v_ g-e）$ {g-e）$。对于顶点$ x $，让$ em（x）$是一组边缘$ e $，以便在p（\ {x \}，e）$的$（x，v）\ in $ g $中存在一个顶点$ v $。如果每个边缘$ e $ o的$ e $ g $ of $ g $的$ g $的$ m $顶点是$ g $的距离 - $ m $，即$ m $的某些顶点，即，套装$ p（m，e）$是非空的。图$ g $的远距离监控号码（$ dem（g）$表示）定义为$ g $的距离边缘监控集的最小尺寸。 $ m $的顶点表示由$ g $建模的网络中的距离探针；当边缘$ e $失败时，从$ x $到$ y $的距离增加，因此我们能够检测到失败。事实证明，我们不仅可以检测到它，而且我们甚至可以正确找到失败的边缘。在本文中，我们继续研究\ emph {距离 - 边缘监测集}。特别是，我们分别给出$ p（m，e）$，$ em（x）$，$ dem（g）$的上限和下限，以及达到界限的极端图。我们还用$ dem（g）= 3 $来表征图形。
Foucaud et al. [Discrete Appl. Math. 319 (2022), 424-438] recently introduced and initiated the study of a new graph-theoretic concept in the area of network monitoring. 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)\neq d_{G-e}(x, y)$. For a vertex $x$, let $EM(x)$ be the set of edges $e$ such that there exists a vertex $v$ in $G$ with $(x, v) \in P(\{x\}, e)$. A set $M$ of vertices of a graph $G$ is 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 a graph $G$, denoted by $dem(G)$, is defined as the smallest size of distance-edge-monitoring sets of $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. It turns out that not only we can detect it, but we can even correctly locate the failing edge. In this paper, we continue the study of \emph{distance-edge-monitoring sets}. In particular, we give upper and lower bounds of $P(M,e)$, $EM(x)$, $dem(G)$, respectively, and extremal graphs attaining the bounds are characterized. We also characterize the graphs with $dem(G)=3$.
