Acta Mechanica Slovaca 2017, 21(1):6-11 | DOI: 10.21496/ams.2017.002

On Minimal Doubly Resolving Sets of Circulant Graphs

Ali Ahmad^1*, Saba Sultan²

¹ College of Computer Science & Information Systems, Jazan University, Jazan, Saudi Arabia

² Abdus Salam School of Mathematical Sciences, GC University, Lahore, Pakistan.

Consider a simple connected undirected graph G = (VG ,EG), where VG represents the vertex set and EG represents the edge set respectively. A subset B of VG is called a resolving set if for every two distinct vertices x, y of G there is a vertex v in set B such that d(x,v) ≠ d(y,v). The resolving set of minimum cardinality is called metric basis of graph G . This minimal cardinality of metric basis is denoted by β(G), and is called metric dimension of G. A subset D of V is called doubly resolving set if for every two vertices x, y of G there are two vertices u, v ∈ D such that d(u,x) -d(u,y) ≠ d(v,x) -d(v,y). A doubly resolving set with minimum cardinality is called minimal doubly resolving set. This minimum cardinality is denoted by ψ(G).
Some partial cases for metric dimension of circulant graph Cn(1,2,3) for n ≥ 12 has been discussed in [21]. Afterwards, problem of finding metric dimension for circulant graph Cn(1,2,3), n ≥ 12 has been completely solved by Borchert et al., in [7].
In this paper, we prove that ψ (Cn (1, 2, 3)) = β (Cn (1, 2, 3)) = {4 if n ≠ 1(mod 6), 5 otherwise.

Keywords: resolving set, metric dimension, minimal doubly resolving set, circulant graph

Published: March 31, 2017  Show citation