For any positive integer l and any graph G=(V,E), a set D of vertices of G is said to be an l-dominating set if every vertex in V(G)-D is at distance at most l from some vertex in D. The l-domination number, γl(G), is the minimum cardinality of an l-dominating set of G. For a given graph G and an integer l, to determine γl(G) is an NP-hard problem. It is proved in this paper that if G is a connected graph of order p with p≥ l+1, then γl(G)≤(p-Δ+l-1)/(l) for any positive integer l. This bound is the best possible for some Δ and l and is an improvement on some known results.%对于任意的正整数l, 连通图G的顶点子集D被称为距离l-控制集,是指对于任意顶点v(∈)D,D中至少含有一个顶点u,使得距离dG(u,v)≤l. 图G距离l-控制数γl(G)是指G中所有距离l-控制集的基数的最小者. 确定图G的距离l-控制数γl(G) 是 NP-问题.给出了当G是阶数为p(p≥ l+1)的连通图时,对于任意的正整数 l,都有最优上界γl(G)≤(p-Δ+l-1)/(l). 而且针对某些Δ和 l,是对Meir和Moon的结果的一种改进.
展开▼
