关于组合星图反馈结点集的下界(英文)  

On lower bound of feedback vertex set of (n,k)-star graph

作　　者：向永红[1] 张德海[1] 向占宏[2] 刘云丽 

机构地区：[1]云南大学软件学院,云南昆明650091 [2]湖南财经高等专科学校信息管理系,湖南长沙410205 [3]云南省电力集团试验研究院软件开发部,云南昆明650041

出　　处：《云南大学学报（自然科学版）》2006年第5期384-387,共4页Journal of Yunnan University(Natural Sciences Edition)

基　　金：Natural Science Foundation of Yunnan Province under Grant (2004F00062);Science Foundation of Yunnan Educational Department under Grant (03Y153D);Natural Science Foundation of Yunnan University under Grant (2003Q022A)

摘　　要：最近诸多文章旨在讨论关于反馈结点集的上下界问题,比如:蝴蝶网、超立方体、网格、星图等等.本文主要讨论了关于组合星图反馈结点集的下界问题,在基于组合星图的性质和已有相关结果的基础上,给出了组合星图反馈结点集的新的下界.A series of recent papers has aimed at giving good bounds of feedback vertex set for families of graphs broadly known as： butterflies, hypercubes, meshes, star graphs, and so on. Compare to existing results for general graph, new lower bound on the size of the minimum feedback vertex set of （ n, k）-star graph is given based on its special structure.

关 键 词：组合星图 反馈结点集 下界 

分 类 号：TP302.7[自动化与计算机技术—计算机系统结构]