关于折叠超立方体的反馈数

On feedback number of folded hypercube

研究了一类重要的互连网络拓扑结构折叠超立方体网络Qfn的反馈数．设F为Qfn的反馈集，通过构造剩余子图G[V（Qfn）-F]的极大无圈子图得到极小反馈集，从而得到反馈数的上界，用此方法研究折叠超立方体网络Qfn的反馈数问题．根据n维折叠超立方体网络的性质，提出一种新的方法构造无圈子图，改进了已有的”维折叠超立方体网络的反馈数的上界．结果表明，当n为奇数时构造的Qfn＋z的无圈导出子图的整体连通性能与已有结论中构造的Q中无圈导出子图R∪Qfon是一致的．

The feedback number of folded hypercube Qfn, which is an important interconnection network topological structure, is researched. Defining F as a feedback vertex set of Qfn, maximal acyclic subgraph of survived subgraph G[V（Qfn）-F] is construted and a minimal feedback vertex set is achieved. By this approach, the upper bound of feedback number of Qfn is obtained. According to the property of n-dimensional folded hypercube, a new approach to constructing acyclic subgraph is presented and the upper bound of feedback number of Qfn is improved. The conclusion indicates that the connectivity of acyclic subgraph of Qfn＋z constructed by the approach is consistent with the one of acyclic subgraph induced by R ∪ Qfon provided by related results when n is odd.