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.

Tasks

• Become familiar with the existing results on MD
• Analyse theoretically the MD of a deterministic graph (e.g. 2D grid) with small perturbations

Required skills

• Strong foundations in probability theory and familiarity with graphs
• Enthusiasm for theoretical research problems
• Familiarity with random graphs is useful

Difficulty: hard

This is a high-risk project with high benefits. In particular, it requires a student who is able to take steps independently.

Applying for the project

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.