On the metric dimension of Grassmann graphs

Abstract

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\ge 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$.

9 pages. Revised to correct an error in Proposition 9 of the previous version

Cited by in corpus (1)

• Metric dimension of some distance-regular graphs