E. Yi

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 dimension


FD1 Graphs and Networks 4
June 11, 2021  2:45 PM
1 - GB Dantzig

Latest news

  • 6/5/21
    Conference abstract book

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.