On r-locating-dominating sets in paths
On r-locating-dominating sets in paths
复制标题
DOI：
10.1016/j.ejc.2008.04.011
复制
发表时间：
2009-05
期刊：
影响因子：
--
通讯作者：
中科院分区：
文献类型：
--
作者：
假设G = (V, E)是一个简单的无向图,和C是一个非空的子集为每个V∈诉,我们定义红外(V) = {u C∣dG∈(u, V)≤r},在dG (u, V)表示边的数量在任何u和V之间的最短路径,如果集红外V (V)∉C是两两不同,并没有一个是空集,我们说C是一组r-locating-dominating在G .结果表明,最小的2-locating-dominating设置路径与n顶点基数⌈(n + 1) / 3⌉,这与之前由Bertrand， Charon， Hudry和Lobstein证明的下界一致。此外，我们还给出了改进Bertrand， Charon， Hudry和Lobstein结果的一般上界。
Assume that G=(V,E) is a simple undirected graph, and C is a nonempty subset of V. For every v∈V, we define Ir(v)={u∈C∣dG(u,v)≤r}, where dG(u,v) denotes the number of edges on any shortest path between u and v. If the sets Ir(v) for v∉C are pairwise different, and none of them is the empty set, we say that C is an r-locating–dominating set in G. It is shown that the smallest 2-locating–dominating set in a path with n vertices has cardinality ⌈(n+1)/3⌉, which coincides with the lower bound proved earlier by Bertrand, Charon, Hudry and Lobstein. Moreover, we give a general upper bound which improves a result of Bertrand, Charon, Hudry and Lobstein.