树的k-分支限制控制数的一个下界

J4 ›› 2010, Vol. 45 ›› Issue (2): 1-4.

• 论文 • 下一篇

树的k-分支限制控制数的一个下界

陈宏宇牛翠霞邹青松

陈宏宇邹青松：山东大学数学学院, 山东济南 250100; 牛翠霞：山东工商学院信电学院, 山东烟台 264005

收稿日期:2008-11-27 出版日期:2010-02-16 发布日期:2010-03-27
作者简介:陈宏宇(1981-),女,博士研究生,主要研究方向为图论与组合最优化. Email: hongyuchen86@163.com
基金资助:
国家自然科学基金资助项目(60373025;60873207,10971121)

A lower bound of k-component restrained domination number in trees

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

Received:2008-11-27 Online:2010-02-16 Published:2010-03-27

摘要/Abstract

摘要：

设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)},而且刻画了可以达到这个下界的树。