On the edge dimension of a graph

Abstract: Given a connected graph

G (V, E)

, the edge dimension, denoted

m a t h r m e d i m (G)

, is the least size of a set

S s u b s e t e q 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

m a t h r m e d i m

. In this article we answer two of these questions: we classify the graphs for which

m a t h r m e d i m (G) = n - 1

and show that

f r a c m a t h r m e d i m (G) d i m (G)

isn't bounded from above (here

d i m (G)

is the standard metric dimension of

G

). We also compute

m a t h r m e d i m (G B o x P_{m})

and

m a t h r m e d i m (G + K_{1})

.

Recommendations

Cites work

Cited in

(69)

This page was built for publication: On the edge dimension of a graph