On a Conjecture About the Local Metric Dimension of Graphs

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 d_G(u, w) ≠ d_G(v, w) where d_G(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 K_n.