论文标题
监视边缘地址集：硬度和图形产品
Monitoring edge-geodetic sets: hardness and graph products
论文作者
论文摘要
Foucaud，Krishna和Lekshmi最近在图中介绍了监视边缘地址集的概念，以及相关的图形不变。这些是一组顶点，以使任何边的去除改变了集合中的一对顶点之间的距离。他们研究了给定图中此类集合的最小可能大小，我们将其称为监视边缘地理编号。 我们表明，监视边缘地理数字的决策问题是NP完成的。我们还为两个图的笛卡尔和强产物提供了最有可能的上限和下限。在许多情况下，这些边界建立了确切的值，包括许多新的图形示例，其仅监视边缘地理位置集是整个顶点集。
Foucaud, Krishna and Lekshmi recently introduced the concept of monitoring edge-geodetic sets in graphs, and a related graph invariant. These are sets of vertices such that the removal of any edge changes the distance between some pair of vertices in the set. They studied the minimum possible size of such a set in a given graph, which we call the monitoring edge-geodetic number. We show that the decision problem for the monitoring edge-geodetic number is NP-complete. We also give best-possible upper and lower bounds for the Cartesian and strong products of two graphs. These bounds establish the exact value in many cases, including many new examples of graphs whose only monitoring edge-geodetic set is the whole vertex set.
