论文部分内容阅读
对简单图G=(V,E),顶点子集F()V,如果由V＼F导出的子图不含圈,则称F是G的反馈点集.点数最小的反馈点集称图的最小反馈点集,最小的点数称为反馈数.一个k维折叠立方体是由一个k维超立方体加上所有的互补边构成的图.本文证明了k维折叠立方体网络的反馈数f(k)=c·2k-1(k≥2), 其中c∈(k-1/k,1].