The metric dimension of circulant graphs

A pair of vertices x and y in a graph G are said to be resolved by a vertex w if the distance from x to w is not equal to the distance from y to w. We say that G is resolved by a subset of its vertices W if every pair of vertices in G is resolved by some vertex in W. The minimum cardinality of a resolving set for G is called the metric dimension of G, denoted by dim(G). The circulant graph Cn(1, 2, . . . , t) is the Cayley graph Cay(Zn : {±1,±2, . . . ,±t}). In this note we prove that, for n = 2kt + 2t, dim(Cn(1, 2, . . . , t)) ≥ t + 2, confirming Conjecture 4.1.2 in [K. Chau, S. Gosselin, The metric dimension of circulant graphs and their Cartesian products, Opuscula Math. 37 (2017), 509–534].

---

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025)