论文标题
关于网格图的度量尺寸的鲁棒性，以添加单个边缘
On the robustness of the metric dimension of grid graphs to adding a single edge
论文作者
论文摘要
图的度量尺寸（MD）是一个组合概念，该概念捕获了基于图形距离区分图中每个节点所需的地标节点数量的最小数量。我们研究如果在图表中添加单个边缘，MD可以增加多少。可以对手选择额外的边缘，在这种情况下，我们对MD可以或随机统一的最大可能值感兴趣，在这种情况下，我们对MD的分布感兴趣。 [Eroh等人已经研究了对抗环境。 Al。，2015年]对于一般图，他找到了一个示例，其中MD在添加单个边缘时会加倍。通过构建一个不同的示例，我们表明这种增加可能与指数一样大。但是，我们认为只有在特殊构造的图中才能发生如此大的增长，并且在最有趣的图族中，添加单个边缘时最多的MD。我们通过证明$ 2D $适当选择的角和额外边缘的端点可以区分每对节点，无论添加边缘如何，我们都可以证明这一点，以$ d $维的网格图。对于$ d = 2 $的特殊情况，我们表明，选择四个角落作为地标是足够的。最后，当随机对额外的边缘进行统一采样时，我们猜想2维网格的MD概率将概率收敛到$ 3+\ \ \ \ \ \ \ \ \ \ \ \ m}（8/27）$，我们给出了几乎完整的证明。
The metric dimension (MD) of a graph is a combinatorial notion capturing the minimum number of landmark nodes needed to distinguish every pair of nodes in the graph based on graph distance. We study how much the MD can increase if we add a single edge to the graph. The extra edge can either be selected adversarially, in which case we are interested in the largest possible value that the MD can take, or uniformly at random, in which case we are interested in the distribution of the MD. The adversarial setting has already been studied by [Eroh et. al., 2015] for general graphs, who found an example where the MD doubles on adding a single edge. By constructing a different example, we show that this increase can be as large as exponential. However, we believe that such a large increase can occur only in specially constructed graphs, and that in most interesting graph families, the MD at most doubles on adding a single edge. We prove this for $d$-dimensional grid graphs, by showing that $2d$ appropriately chosen corners and the endpoints of the extra edge can distinguish every pair of nodes, no matter where the edge is added. For the special case of $d=2$, we show that it suffices to choose the four corners as landmarks. Finally, when the extra edge is sampled uniformly at random, we conjecture that the MD of 2-dimensional grids converges in probability to $3+\mathrm{Ber}(8/27)$, and we give an almost complete proof.
