The metric dimension of Cayley digraphs

A vertex x in a digraph D is said to resolve a pair u  , vv of vertices of D if the distance from u to x   does not equal the distance from vv to x. A set S of vertices of D is a resolving set for D if every pair of vertices of D is resolved by some vertex of S. The smallest cardinality of a resolving set for D  , denoted by dim(D)dim(D), is called the metric dimension for D  . Sharp upper and lower bounds for the metric dimension of the Cayley digraphs Cay(Δ:Γ)Cay(Δ:Γ), where ΓΓ is the group Zn1⊕Zn2⊕⋯⊕ZnmZn1⊕Zn2⊕⋯⊕Znm and ΔΔ is the canonical set of generators, are established. The exact value for the metric dimension of Cay({(0,1),(1,0)}:Zn⊕Zm)Cay({(0,1),(1,0)}:Zn⊕Zm) is found. Moreover, the metric dimension of the Cayley digraph of the dihedral group DnDn of order 2n2n with a minimum set of generators is established. The metric dimension of a (di)graph is formulated as an integer programme. The corresponding linear programming formulation naturally gives rise to a fractional version of the metric dimension of a (di)graph. The fractional dual implies an integer dual for the metric dimension of a (di)graph which is referred to as the metric independence of the (di)graph. The metric independence of a (di)graph is the maximum number of pairs of vertices such that no two pairs are resolved by the same vertex. The metric independence of the n  -cube and the Cayley digraph Cay(Δ:Dn)Cay(Δ:Dn), where ΔΔ is a minimum set of generators for DnDn, are established.