The metric dimension MD(G) of an undirected graphGis the cardinality of a smallest set of vertices that allows, through their distances to all vertices, to distinguish any two vertices ofG. 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 subcubicn-node graphs, all strongly-connected orientations asymptotically have metric dimension at mostn2, and that there are such orientations having metric dimension2n5. We then consider strongly-connected orientations of grids. For a torus withnrows andmcolumns, we show that the maximum value of the metric dimension of a strongly-connected Eulerian orientation is asymptoticallynm2(the equality holding whenn,mare even, which is best possible). For a grid withnrows andmcolumns, we prove that all strongly-connected orientations asymptotically have metric dimension at most2nm3, and that there are such orientations having metric dimensionnm2.
展开▼
