Metric Dimension: from Graphs to Oriented Graphs

Julien Bensmail 1 Fionn Mc Inerney 1 Nicolas Nisse 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
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 n 2 , and that there are such orientations having metric dimension 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 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 2nm 3 , and that there are such orientations having metric dimension nm 2 .
Type de document :
Rapport
[Research Report] Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France. 2018
Liste complète des métadonnées

https://hal.inria.fr/hal-01938290
Contributeur : Fionn Mc Inerney <>
Soumis le : mercredi 28 novembre 2018 - 15:27:56
Dernière modification le : jeudi 29 novembre 2018 - 01:21:43

Fichier

oriented_metric_dimension.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01938290, version 1

Collections

Citation

Julien Bensmail, Fionn Mc Inerney, Nicolas Nisse. Metric Dimension: from Graphs to Oriented Graphs. [Research Report] Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France. 2018. 〈hal-01938290〉

Partager

Métriques

Consultations de la notice

54

Téléchargements de fichiers

30