关于局部扭立方体的反馈数  

On feedback number of locally twisted cube

作　　者：张思佳[1] 徐喜荣[1] 刘聪[1] 曹楠[2] 杨元生[1] 

机构地区：[1]大连理工大学电子信息与电气工程学部,辽宁大连116024 [2]中国科学技术大学数学系,安徽合肥230026

出　　处：《大连理工大学学报》2014年第2期262-266,共5页Journal of Dalian University of Technology

基　　金：国家自然科学基金资助项目(61170303;10671191);高等学校博士学科点专项科研基金资助项目(200801411073)

摘　　要：确定一般网络(或图)的最小反馈点集问题属NP难问题.n维局部扭立方体网络Qltn是n维超立方体网络Qn的变形且是一类重要的互连网络拓扑结构,其拥有的某些性质优于Qn.根据Qltn顶点集合中最后一位字节不同的特点,将其顶点集合划分为两个不相交的子集,通过构造极大无圈子图得到反馈数的上界,并证明了对任意正整数n≥2,存在常数c∈(0,1)使得反馈数为f(n)=2n-1(1-c/(n-1)).The minimum feedback point set problem is known to be NP-hard for general network （graphs）.As an important interconnection network topological structure,the n-dimensional locally twisted cube network Qltn is a new variant of n-dimensional hypercube network Qn,which possesses some properties superior to those of Qn.Since the last bytes in vertex set of Qltn are different,vertex set of Qltn is divided into two disjoint subsets.By constructing a maximal acyclic subgraph of Qltn,the upper limit of feedback number is attained.It is proved that for any positive integer n≥2,there is a constant c∈（0,1）,which makes the feedback number of Qltn as follows：f（n）=2n-1（1-c/n-1）.

关 键 词：局部扭立方体 独立集 无圈子图 反馈数 

分 类 号：O157.9[理学—数学] TP302[理学—基础数学]