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

dmtcs:532 - Discrete Mathematics & Theoretical Computer Science, January 8, 2012, Vol. 13 no. 4 - https://doi.org/10.46298/dmtcs.532
On the metric dimension of Grassmann graphsArticle

Authors: Robert F. Bailey 1; Karen Meagher 1

  • 1 Department of Mathematics and Statistics, [Regina, Saskatchewan]

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.


Volume: Vol. 13 no. 4
Published on: January 8, 2012
Accepted on: June 9, 2015
Submitted on: May 25, 2010
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

4 Documents citing this article

Consultation statistics

This page has been seen 446 times.
This article's PDF has been downloaded 1016 times.