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 C_{n} (? 1, ? 2, ... , ? t) consists of vertices v_{0}, v_{1}, ... , v_{n-1} and undirected edges v_{i} v_{i+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 C_{n} (1, t) consists of vertices v_{0}, v_{1}, ... , v_{n-1} and directed edges v_{i} v_{i+1}, v_{i} v_{i+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 C_{n} (? 1, ? t) are available only for special values of t. We give a complete solution of this problem for directed graphs C_{n} (1, t) for every t ≥ 2 if n ≥ 2t^{2}. 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(C_{n} (? 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(C_{n} (? 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: |