کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651262 | 1342529 | 2006 | 11 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Mathematics - Volume 306, Issue 1, 28 January 2006, Pages 31–41