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
Gq(n,k) (whose vertices are the
k-subspaces of
Fqn, 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 Fqn.
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