关于图的距离控制数的上界(英文)  

Bounds for Distance Domination Numbers of Graphs

作　　者：田方[1] 徐俊明[1] 

机构地区：[1]中国科学技术大学数学系,安徽合肥230026

出　　处：《中国科学技术大学学报》2004年第5期529-534,共6页JUSTC

基　　金：SupportedbyNNSFofChina(10 2 71114and 10 30 10 31)

摘　　要：对于任意的正整数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。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)-Dis 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 ofG. 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-1l for any positive integer l. This bound is the best possible for some Δ and l and is an improvement on some known results.

关 键 词：距离控制数 控制数 直径 

分 类 号：O157.5[理学—数学]