有向笛卡尔积图的有向度量维数

摘要

Abstract For a vertex set W ={Wl,W2,...,wk} of a digraph D and a vertex v C V（D）, the （directed distance） representation of v with respect to W is the ordered k-tuple r（v／W） = （d（v, wl）,d（v, w2）,...,d（v, wk））, and W is a resolving set of D if r（v／W） ~ r（u／W） holds for any pair of distinct vertices u and v. The directed metric dimension of D, denoted by dim（D）, is the cardinality of a smallest resolving set of D. In this paper, we study the directed metric dimension of the Cartesian product digraph D1 x 02. Let Pm and Cm be the directed path and the directed cycle of length m, respectively. A lower bound is given for dim（D1×D2）, and upper bounds are given for dim（D × Pm） and dim（D× Cm）, respectively. The exact values of dim（Pm×Pn）, dim（Cm × Pn）, and dim（Cm ×Cn） are determined, which shows that our upper bounds are sharp.%设D是一个有向图，W={W1,W2…WK）是D的一个有序点子集，u足D中任意一点。我们把有序K元素组r（uW）=（d（u，W1），d（u，W2），…，d（u，Wk））称为点U对于w的（有向距离）表示。如果在D中，任意两个不同的点u和v对W的（有向距离）表示都不相同，则称W是有向图D的一个分解集。我们把D的最小分解集的基数称为有向图D的有向度量维数，并用dim（D）来表示。