On the metric dimension of Grassmann graphs

Robert F. Bailey, Karen Meagher

Published 2010-10-21, updated 2011-11-24Version 3

The {\em metric dimension} of a graph $\Gamma$ 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 $\mathbb{F}_q^n$, and are adjacent if they intersect in a $(k-1)$-subspace) for $k\geq 2$, and find a constructive upper bound on its metric dimension. Our bound is equal to the number of 1-dimensional subspaces of $\mathbb{F}_q^n$.