Skip to Main content Skip to Navigation
Journal articles

Metric Dimension: from Graphs to Oriented Graphs

Fionn Mc Inerney 1 Julien Bensmail 1 Nicolas Nisse 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : The metric dimension $MD(G)$ of an undirected graph $G$ is the cardinality of a smallest set of vertices that allows, through their distances to all vertices, to distinguish any two vertices of $G$. Many aspects of this notion have been investigated since its introduction in the 70's, including its generalization to digraphs. In this work, we study, for particular graph families, the maximum metric dimension over all strongly-connected orientations, by exhibiting lower and upper bounds on this value. We first exhibit general bounds for graphs with bounded maximum degree. In particular, we prove that, in the case of subcubic $n$-node graphs, all strongly-connected orientations asymptotically have metric dimension at most $\frac{n}{2}$, and that there are such orientations having metric dimension $\frac{2n}{5}$. We then consider strongly-connected orientations of grids. For a torus with $n$ rows and $m$ columns, we show that the maximum value of the metric dimension of a strongly-connected Eulerian orientation is asymptotically $\frac{nm}{2}$ (the equality holding when $n$, $m$ are even, which is best possible). For a grid with $n$ rows and $m$ columns, we prove that all strongly-connected orientations asymptotically have metric dimension at most $\frac{2nm}{3}$, and that there are such orientations having metric dimension $\frac{nm}{2}$.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-01938290
Contributor : Fionn Mc Inerney <>
Submitted on : Tuesday, March 30, 2021 - 9:39:27 PM
Last modification on : Thursday, April 1, 2021 - 3:31:07 AM

File

ori_md_DAM_version_HAL.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Fionn Mc Inerney, Julien Bensmail, Nicolas Nisse. Metric Dimension: from Graphs to Oriented Graphs. Discrete Applied Mathematics, Elsevier, In press, ⟨10.1016/j.dam.2020.09.013⟩. ⟨hal-01938290v4⟩

Share

Metrics

Record views

11

Files downloads

125