有向笛卡尔积图的有向度量维数(英文)

The Directed Metric Dimension of Cartesian Product of Digraphs

设D是一个有向图,w={w_1,w_2,…,w_k}是D的一个有序点子集,v是D中任意一点。我们把有序k元素组r(v|w)=(d(v,w_1),d(v,w_2),…,d(v,w_k))称为点v对于W的(有向距离)表示。如果在D中,任意两个不同的点u和v对W的(有向距离)表示都不相同,则称W是有向图D的一个分解集。我们把D的最小分解集的基数称为有向图D的有向度量维数,并用dim(D)来表示。本文研究了有向笛卡尔积图D_1×D_2的有向度量维数。设P_m和C_m分别是长为m的有向路和有向圈。在文中我们分别给出了dim(D_1×D_2)的一个下界与dim(D×P_m)和dim(D×C_m)的上界,并通过确定dim(P_m×P_n),dim(C_m×P_n)和dim(C_m×C_n)的精确值说明了我们给出的上界是紧的。

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.