Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. On the metric dimens ...
Article

On the metric dimension of Grassmann graphs

Robert F. Bailey (1), Karen Meagher (1)
(1) Department of Mathematics and Statistics, [Regina, Saskatchewan]
Download article
Open on HAL
Imported on
May 24, 2010
Published on
January 7, 2012
Last modified on
March 31, 2025
Volume 13
vol. 13:4, Special Issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity
DOI
10.46298/dmtcs.532
License
https://about.hal.science/hal-authorisation-v1
Natural Sciences and Engineering Research Council of Canada
Indicators
948
Views
1529
Downloads

On the metric dimension of Grassmann graphs

Robert F. Bailey (1), Karen Meagher (1)
(1) Department of Mathematics and Statistics, [Regina, Saskatchewan]
Abstract
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Cited by

Source: OpenCitations

  • Joint Privacy and Security of Multiple Biometric Systems

    Cambridge University Press eBooks

    Authors : A. Goldberg ORCID, S. C. Draper ORCID

    Journal reference : Volume , 2017, pp. 445-472

    DOI : 10.1017/9781316450840.017

  • The Metric Dimension of a Class of Halved Folded n-Cube

    Advances in Applied Mathematics

    Authors : 毅 田

    Journal reference : Volume 14, 2025, pp. 54-58

    DOI : 10.12677/aam.2025.147346

  • Variable neighborhood search for metric dimension and minimal doubly resolving set problems

    European Journal of Operational Research

    Authors : Nenad Mladenović ORCID, Jozef Kratica ORCID, Vera Kovačević-Vujčić, Mirjana Čangalović

    Journal reference : Volume 220, 2012, pp. 328-337

    DOI : 10.1016/j.ejor.2012.02.019

  • Optimizing SNARK networks via double metric dimension

    AIMS Mathematics

    Authors : Muhammad Ahmad ORCID, Muhammad Faheem ORCID, Sanaa A. Bajri ORCID, Zohaib Zahid ORCID, Muhammad Javaid ORCID, Hamiden Abd El-Wahed Khalifa ORCID

    Journal reference : Volume 9, 2024, pp. 22091-22111

    DOI : 10.3934/math.20241074

  • On Resolvability- and Domination-Related Parameters of Complete Multipartite Graphs

    Mathematics

    Authors : Sakander Hayat ORCID, Asad Khan ORCID, Yubin Zhong

    Journal reference : Volume 10, 2022, pp. 1815

    DOI : 10.3390/math10111815

  • An Upper Bound on the Metric Dimension of the Halved Folded n-Cube

    Pure Mathematics

    Authors : 毅 田

    Journal reference : Volume 15, 2025, pp. 53-60

    DOI : 10.12677/pm.2025.157206

  • Metric Dimension of 4-Regular Cyclic Bipartite Graphs

    Malaysian Journal of Mathematical Sciences

    Authors : K. Bharani Dharan, S. Radha

    Journal reference : Volume 19, 2025, pp. 1397

    DOI : 10.47836/mjms.19.4.12

  • A Study on Minimal Doubly Resolving Sets of Certain Families of Networks

    IEEE Access

    Authors : Muhammad Ahmad ORCID, Zohaib Zahid ORCID, Muhammad Javaid ORCID, Mamo Abebe Ashebo ORCID

    Journal reference : Volume 11, 2023, pp. 56344-56352

    DOI : 10.1109/access.2023.3282701
Preview
Loading PDF preview...