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 -
On the metric dimension of Grassmann graphs

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]
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.2307/2006997
  • 10.2307/2006997
On the Order of Uniprimitive Permutation Groups

2 Documents citing this article

Consultation statistics

This page has been seen 291 times.
This article's PDF has been downloaded 827 times.