期刊
DISCRETE APPLIED MATHEMATICS
卷 155, 期 3, 页码 356-364出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.dam.2006.06.009
关键词
strong dimension; vertex covering number; weak and unilateral dimension of digraphs
Let G be a connected (di)graph. A vertex omega is said to strongly resolve a pair u, nu of vertices of G if there exists some shortet U-omega) path containing nu or some shortest nu-omega; path containing u. A set W of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of W. The smallest cardinality of a strong resolving set for G is called the strong dimension of G. It is shown that the problem of finding the strong dimension of a connected graph can be transformed to the problem of finding the vertex covering number of a graph. Moreover, it is shown that computing this invariant is NP-hard. Related invariants for directed graphs are defined and studied. (c) 2006 Elsevier B.V. All tights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据