The metric dimension of Cayley digraphs

Autor: Shonda Gosselin, Ortrud R. Oellermann, Melodie Fehr
Rok vydání: 2006
Předmět:
Zdroj: Discrete Mathematics. 306:31-41
ISSN: 0012-365X
Popis: 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(@D:@C), where @C is the group Z"n"""[email protected]?Z"n"""[email protected][email protected]?Z"n"""m and @D is the canonical set of generators, are established. The exact value for the metric dimension of Cay({(0,1),(1,0)}:Z"[email protected]?Z"m) is found. Moreover, the metric dimension of the Cayley digraph of the dihedral group D"n 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(@D:D"n), where @D is a minimum set of generators for D"n, are established.
Databáze: OpenAIRE
Externí odkaz: