Metric Dimension and Determining Number of Cayley Graphs
Imran Javaid, Muhammad Naeem Azhar, Muhammad Salman · 2012
Abstract: A subset W of vertices of a graph G is called a resolving set for G if for every pair of distinct vertices u and v of G, there exists a vertex w∈W such that the distance between u and w is different from the distance between v and w. A resolving set containing a minimum number of vertices is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by β(G). A subset S of vertices of a graph G is called a determining set if whenever two automorphisms agree on the elements of S, they agree on all of G. The minimum cardinality of a determining set of G is called the determining number of G, denoted by Det(G). In this paper, we find the metric dimension of Cayley graphs, Cay(Zn: S) for all n≥7 and S = {±1,±3}. Also we show that, for all prime numbers n = 2p+1 with p prime and any subset S of Z n \\{0} with S =-S, S ≠φ and S ≠ Z n \\{0}, Det(Cay(Z n:S))=2.