Graphs and Combinatorics (2023) 39:5 https://doi.org/10.1007/s00373-022-02601-z O R I G I N A L P A P E R On a Conjecture About the Local Metric Dimension of Graphs Ali Ghalavand 1 · Michael A. Henning2 · Mostafa Tavakoli1 Received: 23 April 2022 / Revised: 20 October 2022 / Accepted: 16 November 2022 © The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature 2022 Abstract 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−1 k ) 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 .

Keywords