On Edge Dimension of a Graph

2016/11/07 by Zubrilina, Nina · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1611.01904

Abstract

Given a connected graph G(V, E), the edge dimension, denoted edim(G), is the least size of a set S ⊆ V that distinguishes every pair of edges of G, in the sense that the edges have pairwise distinct tuples of distances to the vertices of S. The notation was introduced by Kelenc, Tratnik, and Yero, and in their paper, they asked several questions about properties of edim. In this article we answer two of these questions: we classify the graphs for which edim(G) = n-1 and show that (edim(G))/(dim(G)) isn't bounded from above (here dim(G) is the standard metric dimension of G). We also compute edim(G\Box P_m) and edim(G + K₁).

Cited by

• Throttling for metric dimension and its variants
• Distance-based (and path-based) covering problems for graphs of given cyclomatic number

Related

• Uniquely identifying the edges of a graph: the edge metric dimension
• A note on the metric and edge metric dimensions of 2-connected graphs
• Metric dimension and edge metric dimension of unicyclic graphs
• Graphs with the edge metric dimension smaller than the metric dimension
• Edge metric dimension of some graph operations