点击次数：

论文类型：期刊论文

发表时间：2016-05-15

发表刊物：计算机科学

收录刊物：PKU、ISTIC、CSCD

卷号：43

期号：5

页面范围：13-21

ISSN号：1002-137X

关键字：互联网络拓扑结构;反馈点集;反馈数;广义Kautz有向图;无圈子图

摘要：对于给定的图G的顶点集的子集F,如果删除F使得剩余子图是无圈子图,则称子集F为图G的反馈点集.研究了广义Kautz有向图GK(d,n)的反馈点集.令f(d,n)表示广义Kautz有向图GK(d,n)的所有反馈集合中顶点个数最少的集合的个数(即广义Kautz有向图GK(d,n)的反馈数),给出了GK(3,n)的反馈数的上界,即f(3,n)≤n+「5n/8」-「3n/4」-「4n/7」+3.