A resolving set of a graph G is a subset of nodes R such that any two nodes of G is a different distance away from at least one point in R. The Metric Dimension (MD) of G is the minimum cardinality of such a set. The MD and the corresponding resolving set are shown below for some simple graphs.
The MD has been studied for several families of deterministic graphs, and recently for Erdos-Renyi random graphs. An interesting fact about the MD is that it is not a monotone graph property (i.e. adding or removing edges can both increase and decrease the MD), and it in general seams much less robust than other well-studied properties (e.g. max clique size). The goal of this project is to better understand the robustness of MD.
This is a high-risk project with high benefits. In particular, it requires a student who is able to take steps independently.
This semester project is aimed at one Master's student with strong theory background. For applying please send your relevant courses and CV to Gergely Odor.