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.
翻译：Foucaud、Krishna和Lekshmi最近引入了在图表中监测边缘地极组和相关的图表变量的概念。 这些是脊椎的组合, 使任何边缘的移走能够改变组合中某些脊椎之间的距离。 他们研究了特定图表中这种组合的最小可能大小, 我们称之为监测边缘地极数。 我们显示, 监测边缘地极数的决定问题是 NP 完整的。 我们还给出了两种图表中最有可能达到的上下界, 以及强力产品 。 这些界限确定了许多情况下的准确价值, 包括许多新的图表例子, 这些图表仅监测边缘地极地极组是整个脊椎组。
相关内容
微信扫码咨询专知VIP会员