On a Conjecture About the Local Metric Dimension of Graphs

Ali Ghalavand, Michael A. Henning, Mostafa Tavakoli

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


Let G be a connected graph. A subset S of V(G) is called a local metric generator for G if for every two adjacent vertices u and v of G there exists a vertex w∈ S such that dG(u, w) ≠ dG(v, w) where dG(x, y) is the distance between vertices x and y in G. The local metric dimension of G, denoted by dim (G) , is the minimum cardinality among all local metric generators of G. The clique number ω(G) of G is the cardinality of a maximum set of vertices that induce a complete graph in G. The authors in [Local metric dimension for graphs with small clique numbers. Discrete Math. 345 (2022), no. 4, Paper No. 112763] conjectured that if G is a connected graph of order n with ω(G) = k where 2 ≤ k≤ n, then dimℓ(G)≤(k-1k)n. In this paper, we prove this conjecture. Furthermore, we prove that equality in this bound is satisfied if and only if G is a complete graph Kn.

Original languageEnglish
Article number5
JournalGraphs and Combinatorics
Issue number1
Publication statusPublished - Feb 2023


  • Clique
  • Local metric dimension
  • Local metric generator

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'On a Conjecture About the Local Metric Dimension of Graphs'. Together they form a unique fingerprint.

Cite this