ON A GENERALIZED METRIC DIMENSION WITH PARTIALLY KNOWN GRAPH TOPOLOGY

version plus longue de la version courte de GlobalSIPInternational audienceThe metric dimension of a connected graph G is the minimum number of vertices in a subset S of the vertex set of G such that all other vertices are uniquely determined by their distances to the vertices in S. We introduce and analyze the concept of generalized metric dimension of a disconnected graph, which corresponds to the minimum number of vertices in a subset S such that all other vertices have unique distances to it in all connected graphs that result from completing a given disconnected graph. This generalization allows for incomplete knowledge of the underlying graph in applications such as identifying sources of infection. We quantify the generalized metric dimension exactly when the disconnected components are trees, cycles, grids, complete graphs and give general upper bounds on this number in terms of the boundary of the graph