| 树的k-分支限制控制数的一个下界 |
| |
| 引用本文： | 陈宏宇,牛翠霞,邹青松. 树的k-分支限制控制数的一个下界[J]. 山东大学学报(理学版), 2010, 45(2): 1-4 |
| |
| 作者姓名： | 陈宏宇 牛翠霞 邹青松 |
| |
| 作者单位： | 1. 山东大学数学学院,山东,济南,250100
2. 山东工商学院信电学院,山东,烟台,264005 |
| |
| 摘 要： | 设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)},而且刻画了可以达到这个下界的树。
|
| 关 键 词： | 限制控制 k-分支限制控制数 树 |
| 收稿时间： | 2008-11-27 |
A lower bound of k-component restrained domination number in trees |
| |
| CHEN Hong-yu,NIU Cui-xia,ZOU Qing-song. A lower bound of k-component restrained domination number in trees[J]. Journal of Shandong University, 2010, 45(2): 1-4 |
| |
| Authors: | CHEN Hong-yu NIU Cui-xia ZOU Qing-song |
| |
| Affiliation: | CHEN Hong-Yu, ZOU Qing-Song：School of Mathematics, Shandong University, Jinan 250100, Shandong, China; NIU Cui-Xia ： School of Information ＆ Electronic Engineering, Shandong Institute of Business and Technology, Yantai 264005, Shandong, China |
| |
| Abstract: | Let G = (V,E) be a graph.A k-component restrained dominating set is a subset S (C)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 tress T of order n achieving this lower bound are characterized. |
| |
| Keywords: | restrained domination k-component restrained domination number tree |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《山东大学学报(理学版)》浏览原始摘要信息 |
|
点击此处可从《山东大学学报(理学版)》下载全文 |
|
