Exploring Metric Dimension on Random Graphs

Carter Tillquist
CSU Chico

Stevenson 1300
12:00 PM

The metric dimension of a graph G=(V,E) is the smallest number of nodes required to uniquely identify all nodes in G based on shortest path distances. This concept is closely related to trilateration, the idea underlying the Global Positioning System (GPS), and has applications in navigation and in generating embeddings for symbolic data analysis. In this talk, we discuss previous work and preliminary results related to the behavior of metric dimension in the context of Hamming graphs and several random graph models. Bounds on metric dimension and efficient heuristic algorithms for identifying close to optimal solutions are covered.