Bailey, Robert F. and Meagher, Karen - On the metric dimension of Grassmann graphs

dmtcs:532 - Discrete Mathematics & Theoretical Computer Science, January 8, 2012, Vol. 13 no. 4
On the metric dimension of Grassmann graphs

Authors: Bailey, Robert F. and Meagher, Karen

The 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 F-q(n), and are adjacent if they intersect in a (k 1)-subspace) for k \textgreater= 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.


Source : oai:HAL:hal-00990476v1
Volume: Vol. 13 no. 4
Published on: January 8, 2012
Submitted on: May 25, 2010
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 47 times.
This article's PDF has been downloaded 488 times.