Kelenc et al. [Discrete Appl. Math. 251 (2018) 204-220] introduced the notion of edge dimension, a variant of metric dimension. Assuming that some vertices are equipped with landmarks (or sensors), the question is the minimum number of such landmarks needed in order for a robot to know its location from the landmarks at all times as the robot moves from edge to edge. The edge dimension of a graph G is the minimum cardinality of a subset of vertices of G such that every edge of G is uniquely determined by its vector of distances to the chosen vertices.
In this talk, we obtain some general results on edge dimension and initiate the study of fractional edge dimension. We show that the set of edge metric coordinates does not uniquely determine a graph and that edge dimension is not a monotone parameter on subgraph inclusion. We examine the relation between planarity and the graphs with edge dimension two. We also compare fractional metric dimension and fractional edge dimension, among others.
Keywords: metric dimension, edge dimension, fractional metric dimension, fractional edge dimensionScheduled
FD1 Graphs and Networks 4
June 11, 2021 2:45 PM
1 - GB Dantzig