The metric dimension of circulant graphs and Cayley hypergraphs

Abstract

Let G = (VyE) be a connected graph (or hypergraph) and let d(x,y) denote the distance between vertices xty 6 V(G). A subset W ⊆ V(G) is called a resolving set for G if for every pair of distinct vertices xy ϵ V(G), there is iu € W such that d(xtw) ≠ d(t/,tu). The minimum cardinality of a resolving set for G is called the metric dimension of G, denoted by /3(G). In this paper we determine the exact metric dimension of the circulant graphs C_n( 1,2) and C(l, 2,3) for all n, extending previous results due to Javaid and Rahim (2008) and Imran, Baig, Bokhary and Javaid (2011). In particular, we show that β(C_n( 1,2)) = 4 if n = l(mod 4) and 0{Gn{ 1,2)) = 3 otherwise. We also show that β(Gn( 1,2,3)) = 5 if n = l(mod 6) and β(C_n( 1,2,3)) = 4 otherwise. In addition, we bound the metric dimension of Cayley hypergraphs on finite Abelian groups with the canonical set of generators, and we show that the metric dimension of these hypergraphs is related to the metric dimension of a Cartesian product of circulant graphs. © 2018 Utilitas Mathematica Publishing Inc. All rights reserved.