We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
On a Conjecture About the Local Metric Dimension of Graphs.
- Authors
Ghalavand, Ali; Henning, Michael A.; Tavakoli, Mostafa
- 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 .
- Publication
Graphs & Combinatorics, 2023, Vol 39, Issue 1, p1
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-022-02601-z