On the Metric Dimension of Directed and Undirected Circulant Graphs

Abstract

The undirected circulant graph Cn(±1, ±2, . . . , ±t) consists of vertices v0, v1, . . . , vn−1 and undirected edges vivi+j, where 0 ≤ i ≤ n − 1, 1 ≤ j ≤ t (2 ≤ t ≤ n2{n \over 2} ), and the directed circulant graph Cn(1, t) consists of vertices v0, v1, . . . , vn−1 and directed edges vivi+1, vivi+t, where 0 ≤ i ≤ n − 1 (2 ≤ t ≤ 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] presented a conjecture saying that dim (Cn(±1, ±2, . . . , ±t)) = t + p − 1 for n = 2tk + t + p, where 3 ≤ p ≤ t + 1. We disprove it by showing that dim (Cn(±1, ±2, . . . , ±t)) ≤ t + p+12{{p + 1} \over 2} for n = 2tk + t + p, where t ≥ 4 is even, p is odd, 1 ≤ p ≤ t + 1 and k ≥ 1.

Keywords

• metric dimension
• resolving set
• circulant graph
• distance
• 05c35
• 05c12