Release Time:2019-03-10  Hits:

Indexed by: Journal Article

Date of Publication: 2016-05-15

Journal: 计算机科学

Included Journals: CSCD、ISTIC、PKU

Volume: 43

Issue: 5

Page Number: 13-21

ISSN: 1002-137X

Key Words: 互联网络拓扑结构;反馈点集;反馈数;广义Kautz有向图;无圈子图

Abstract: 对于给定的图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.