### On the metric dimension of Grassmann graphs

*Robert F Bailey, Karen Meagher*

#### Abstract

The

*metric dimension*of a graph Γ is the least number of vertices in a set with the property that the list of distances from any vertex to those in the set uniquely identifies that vertex. We consider the Grassmann graph G_{q}(n,k) (whose vertices are the k-subspaces of F_{q}^{n}, and are adjacent if they intersect in a (k-1)-subspace) for k≥2. We find an upper bound on its metric dimension, which is equal to the number of 1-dimensional subspaces of F_{q}^{n}. We also give a construction of a resolving set of this size in the case where k+1 divides n, and a related construction in other cases.Full Text: PDF PostScript