On the metric dimension of Grassmann graphs

Details On the metric dimension of Grassmann graphs On the metric dimension of Grassmann graphs

2010-10-21

arxiv.org/abs/1010.4495v3

Mathematics

Combinatorics

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

Scientific paper

The {\em 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 $\mathbb{F}_q^n$, and are adjacent if they intersect in a $(k-1)$-subspace) for $k\geq 2$, and find a constructive upper bound on its metric dimension. Our bound is equal to the number of 1-dimensional subspaces of $\mathbb{F}_q^n$.

Affiliated with

Also associated with

No associations

Rating

On the metric dimension of Grassmann graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the metric dimension of Grassmann graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the metric dimension of Grassmann graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-423797