14:00
15:00

(Uniquement en présentiel / Only offline, no online version)

The Metric Dimension problem consits in identifying vertices in a graph. The Metric Dimension of a graph G is the minimum cardinality of a subset S of vertices of G such that each vertex of G is uniquely determined by its distances to S. In a general case, add a vertex to a graph can drastically change its metric dimension, we prove we can bound this gap when the initial graph is the tree and one add several edges. To prove this result, we built a valid (but not minimal) set S which size can be bounded efficiently if the graphe is sparse enough.

Joint work with Nicolas Bousquet, Aline Parreau and Ignacio Pelayo.

[Quentin Deschamps] (LIRIS)

https://liris.cnrs.fr/page-membre/quentin-deschamps

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .

LaBRI (178)