摘要
设G=(V,E)是一个图。集合S■V称为一个k-分支限制控制集,如果S是一个限制控制集且G[S]最多有k个分支。G的k-分支限制控制数是G的最小k-分支限制控制集的基数,记作γkr(G)。证明了若树T有n个顶点,则γkr(T)≥max{「n+2/3┐,n-2(k-1)},而且刻画了可以达到这个下界的树。
Let G = （ V, E） be a graph. A k-component restrained dominating set is a subset S lohtain in V which S is a restrained dominating set and G[ S] has at most k components. The k-component restrained domination number of G, denoted by γr^k （G）, is the smallest cardinality of a k-component restrained dominating set of G. It is proved that if T is a tree of order n, then
γr^k（T）≥max{[n＋2/3],n-2（k-1）}.Moreover, the extremal trees T of order n achieving this lower bound are characterized.
出处
《山东大学学报（理学版）》
CAS
CSCD
北大核心
2010年第2期1-4,9,共5页
Journal of Shandong University(Natural Science)
基金
国家自然科学基金资助项目(60373025
60873207
10971121)
关键词
限制控制
k-分支限制控制数
树
restrained domination
k-component restrained domination number
tree
