The metric dimension of Cayley digraphs

• Published in: Discrete mathematics 2006-01, Vol.306 (1), p.31-41
• Main Authors: Fehr, Melodie, Gosselin, Shonda, Oellermann, Ortrud R.
• Format: Article
• Language: English
• Subjects: Applied sciences; Cayley digraphs; Combinatorics; Combinatorics. Ordered structures; Exact sciences and technology; Graph theory; Integer programming; Linear programming; Mathematical programming; Mathematics; Metric dimension; Metric independence; Operational research and scientific management; Operational research. Management science; Sciences and techniques of general use
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/j.disc.2005.09.015

A vertex x in a digraph D is said to resolve a pair u, v of vertices of D if the distance from u to x does not equal the distance from v 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 ) , is called the metric dimension for D. Sharp upper and lower bounds for the metric dimension of the Cayley digraphs Cay ( Δ : Γ ) , where Γ is the group Z n 1 ⊕ Z n 2 ⊕ ⋯ ⊕ Z n m and Δ is the canonical set of generators, are established. The exact value for the metric dimension of Cay ( { ( 0 , 1 ) , ( 1 , 0 ) } : Z n ⊕ Z m ) is found. Moreover, the metric dimension of the Cayley digraph of the dihedral group D n of order 2 n 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 ( Δ : D n ) , where Δ is a minimum set of generators for D n , are established.