Hits:

Indexed by:期刊论文

Date of Publication:2016-05-15

Journal:计算机科学

Included Journals:PKU、ISTIC、CSCD

Volume:43

Issue:5

Page Number:13-21

ISSN No.: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.