| 树图的全控制数 |
| |
| 引用本文： | 侯新民. 树图的全控制数[J]. 中国科学技术大学学报, 2006, 36(6): 604-606 |
| |
| 作者姓名： | 侯新民 |
| |
| 作者单位： | 中国科学技术大学数学系,安徽合肥,230026 |
| |
| 摘 要： | 设G为n阶连通图，集合S称为图G的全控制集，如果V（G）的每个顶点都和S中某点相邻。图G的全控制数，记为γt（G），是图G的全控制集的最小基数。证明了对阶数n≥3且T≠K1，n-1的树T，γt（T）=min{（2n/3），n-l，[n/2]＋l-1}，这里l表示树T中叶子的数目。
|
| 关 键 词： | 全控制集 全控制数 |
| 文章编号： | 0253-2778(2006)06-0604-03 |
| 收稿时间： | 2005-01-19 |
| 修稿时间： | 2005-12-15 |
On the total domination number of trees |
| |
| HOU Xin-min. On the total domination number of trees[J]. Journal of University of Science and Technology of China, 2006, 36(6): 604-606 |
| |
| Authors: | HOU Xin-min |
| |
| Affiliation: | Department of Mathematics, University of Science and Technology of China, Hefei 230026, China |
| |
| Abstract: | For a given connected graph G of order n, a set S of vertices of G is a total dominating set, if every vertex of V(G) is adjacent to some vertex in S. The total domination number of G, denoted by γt(G), is the minimum cardinality of a total dominating set of G. We prove that, if T is a tree of order n>1 and T≠K1,n-1, then γt(T)≤min{(2n)/(3), n-l,([n/2])+l-1}, where l is the number of leaves of T. |
| |
| Keywords: | total dominating set total domination number |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
