论文标题
监视图中的边缘地址集
Monitoring edge-geodetic sets in graphs
论文作者
论文摘要
我们在网络监视领域引入了一个新的图理论概念。在此领域，人们希望监视网络的顶点和/或边缘（被视为图形），以检测和防止故障。受到文献中研究的两个概念的启发（边缘地址集和距离边缘监控集），我们定义了一个监视的边缘地址集（MEG-SET）的概念，将图形$ g $作为边缘地点套件$ s \ subseteq v（g subseteq v（g）的$ g $ $ g $ g expe $ g shore $ g shore $ g shore $ g s of $ g shore $ g s of $ g shore $ gess对于$ g $的每个边缘$ e $ $ e $，都有一个顶点$ x，y $ s $ $ s $，使得$ e $都在$ x $和$ y $之间的所有最短路径上。动机是，如果从网络中删除了某些边缘$ e $（例如，如果它停止了功能），则监视探针$ x $和$ y $将检测到故障，因为它们之间的距离将增加。 我们通过得出某些基本图形类（树，周期，独立图形，完整的图，网格，超级管，高管，Corona产品...）的MEG-set的最小尺寸来探索MEG-套的概念，我们证明了使用图的反馈边缘的上限。 我们还表明，确定图的MEG集的最小尺寸是NP-固定的，即使对于最大程度的最高图最多也是〜9。
We introduce a new graph-theoretic concept in the area of network monitoring. In this area, one wishes to monitor the vertices and/or the edges of a network (viewed as a graph) in order to detect and prevent failures. Inspired by two notions studied in the literature (edge-geodetic sets and distance-edge-monitoring sets), we define the notion of a monitoring edge-geodetic set (MEG-set for short) of a graph $G$ as an edge-geodetic set $S\subseteq V(G)$ of $G$ (that is, every edge of $G$ lies on some shortest path between two vertices of $S$) with the additional property that for every edge $e$ of $G$, there is a vertex pair $x, y$ of $S$ such that $e$ lies on all shortest paths between $x$ and $y$. The motivation is that, if some edge $e$ is removed from the network (for example if it ceases to function), the monitoring probes $x$ and $y$ will detect the failure since the distance between them will increase. We explore the notion of MEG-sets by deriving the minimum size of a MEG-set for some basic graph classes (trees, cycles, unicyclic graphs, complete graphs, grids, hypercubes, corona products...) and we prove an upper bound using the feedback edge set of the graph. We also show that determining the smallest size of an MEG-set of a graph is NP-hard, even for graphs of maximum degree at most~9.
