On the robustness of the metric dimension to adding a single edge

Satvik Mashkaria, Gergely Ódor, Patrick Thiran

Published 2020-10-21Version 1

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. The MD has been connected with the number of sensor nodes required in several applications, including diffusion source detection, navigation and pattern matching. In this paper, we study how much the MD can change if we add a single edge to the graph. We find that the MD cannot decrease by more than two, however, there are examples where the increase can be very large. We believe that such a large increase can occur only in specially constructed graphs. For two simple families of graphs - ring graphs and grid graphs - we show that the increase of the MD cannot be larger than two either. For grid graphs, when the extra edge is sampled uniformly randomly, we almost completely characterize the limiting distribution of the MD.