On the metric dimension of Grassmann graphs

2010/10/21 by R. A. Bailey, Robert F. Bailey, Bailey, Robert F. +2
Computer Science · Engineering · Mathematics · #05C12 (primary) #05E30 (secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems #math.CO #msc:05C12 #msc:05E30

paper · pdf · doi:10.48550/arxiv.1010.4495

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

openalex publication_date 2010/10/21 · arxiv created 2011/11/24 · arxiv updated 2011/11/28 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28

Abstract

The \em 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 G_q(n,k) (whose vertices are the k-subspaces of \mathbbF_qⁿ, and are adjacent if they intersect in a (k-1)-subspace) for k≥ 2, and find a constructive upper bound on its metric dimension. Our bound is equal to the number of 1-dimensional subspaces of \mathbbF_qⁿ.

Related

• Metric dimension of some distance-regular graphs
• The k-metric dimension of graphs: a general approach
• Graphs with the edge metric dimension smaller than the metric dimension
• The k-metric dimension of a graph
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and its Applications