The metric dimension of Cayley digraphs |
| |
Authors: | Melodie Fehr Ortrud R Oellermann |
| |
Institution: | Department of Mathematics and Statistics, The University of Winnipeg, 515 Portage Avenue, Winnipeg, Man., Canada R3B 2E9 |
| |
Abstract: | 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 Zn1⊕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) is found. Moreover, the metric dimension of the Cayley digraph of the dihedral group Dn of order 2n 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), where Δ is a minimum set of generators for Dn, are established. |
| |
Keywords: | Metric dimension Cayley digraphs Metric independence Integer programming Linear programming |
本文献已被 ScienceDirect 等数据库收录! |
|