The metric dimension, also known as the resolvability, of a graph is a fundamental concept in graph theory that measures the smallest number of vertices (called resolving set) required to uniquely identify each vertex in the graph. Research in the metric dimension of graphs is an active area of study, and several interesting problems have been investigated. While I cannot provide you with the absolute top-rated problems as research is constantly evolving, I can mention some important and well-studied problems in this field:
Metric dimension of specific graph classes: Investigating the metric dimension of specific families of graphs is an ongoing research direction. Examples include trees, grids, hypercubes, planar graphs, random graphs, and various graph products. Understanding the metric dimension of these graph classes and finding tight bounds is a challenging problem.
Algorithms for metric dimension: Designing efficient algorithms for computing the metric dimension of a graph is an important research problem. Developing both exact and approximation algorithms, as well as exploring their complexity and performance guarantees, is an active area of study.
Metric dimension invariants: Exploring different graph invariants related to the metric dimension is another research direction. For example, investigating the relationship between the metric dimension and other graph parameters like the diameter, girth, connectivity, or chromatic number of a graph can lead to interesting insights.
Structural properties of resolving sets: Studying the structural properties of resolving sets is an important problem in metric dimension research. Understanding the existence and properties of optimal resolving sets, such as those with minimum size or maximum connectivity, is of interest. Additionally, investigating the relationship between the metric dimension and other graph properties, such as vertex covers or dominating sets, can provide further insights.
Metric dimension of infinite graphs: Extending the study of metric dimension to infinite graphs is a challenging and relatively unexplored area. Investigating the metric dimension of infinite graphs and determining the influence of various graph properties can contribute to the understanding of infinite graph structures.
These are just a few examples of research problems in the metric dimension (resolvability) of graphs. The field is vast, and there are numerous other interesting questions and directions that researchers continue to explore.
Some recent interesting variations are multiset dimension (see Simanjuntak et al.), local multiset dimension, non-local multiset dimension and outer multiset dimension (see Klavzar et al.) All of these are based on the idea of resolving vertices based on the multiset of distances without associating the distances with specific landmarks. An article that came out this week is 'resolving vertices of graphs with differences'.