Authors: T. Vetrik Title: On the metric dimension of directed and undirected circulant graphs Source: Discussiones Mathematicae Graph Theory Received 25.05.2017, Revised 23.01.2018, Accepted 23.01.2018, doi: 10.7151/dmgt.2110 Abstract: The undirected circulant graph Cn (? 1, ? 2, ... , ? t) consists of vertices v0, v1, ... , vn-1 and undirected edges vi vi+j, where 0 \le i \le n-1, 1 \le j \le t (2 \le t \le \frac{n}{2}), and the directed circulant graph Cn (1, t) consists of vertices v0, v1, ... , vn-1 and directed edges vi vi+1, vi vi+t, where 0 \le i \le n-1 (2 \le t \le n-1), the indices are taken modulo n. Results on the metric dimension of undirected circulant graphs Cn (? 1, ? t) are available only for special values of t. We give a complete solution of this problem for directed graphs Cn (1, t) for every t ≥ 2 if n ≥ 2t2. Grigorious et al. [ On the metric dimension of circulant and Harary graphs, Appl. Math. Comput. 248 (2014) 47--54] pre-sented a conjecture saying that dim(Cn (? 1, ? 2, ... , ? t)) = t+p-1 for n=2tk+t+p, where 3 \le p \le t+1. We disprove it by showing that dim(Cn (? 1, ? 2, ... , ? t)) \le t + \frac{p+1}{2} for n=2tk+t+p, where t ≥ 4 is even, p is odd, 1 \le p \le t+1 and k ≥ 1. Keywords: metric dimension, resolving set, circulant graph, distance Links: PDF