摘要
对于给定的图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。
A subset of vertices of a graph Gis called a feedback vertex set of G,if its removal results is an acyclic subgraph.This paper investigated the feedback vertex set of generalized Kautz digraphs GK（d,n）.Let f（d,n）denote the minimum cardinality over all feedback vertex sets of the Generalized Kautz digraph GK（d,n）.The upper bound of the feedback numbers of GK（3,n）is obtained as follows f（3,n）≤n＋[5n/8]-[3n/4]-[4n/7]＋3.
出处
《计算机科学》
CSCD
北大核心
2016年第5期13-21,共9页
Computer Science
基金
国家自然科学基金项目(61472465
61170303)
辽宁省自然科学基金项目(L2013337)资助
关键词
互联网络拓扑结构
反馈点集
反馈数
广义Kautz有向图
无圈子图
Topological structure of interconnection network
Feedback vertex set
Feedback number
Generalized Kautz digraphs
Acyclic subgraph
