折叠超立方体的容错泛圈性

摘要

对于图G，顶点的个数称为图G的阶，用v(G)表示；最小圈的长度称为图G的围长，用g(G)表示.如果图G中存在由k到v(G)之间每个长度的圈，那么称图G是k-泛圈的；如果G是g(G)-泛圈的，那么称图G是泛圈的.如果G的每条边都在长为g(G)到v(G)的圈中，那么称图G是边泛圈的.如果圈中所有的边都是非故障边并且所有的点都是非故障点则称该圈是无错圈.令F表示图G的故障集，fv，fe分别表示F中故障点和故障边的个数.本文研究折叠超立方体的弧传递性和容错泛圈性.证明了折叠超立方体FQn是弧传递的，偶数维折叠超立方体在有一个故障点的情况下任意-条边都在长为n+1到2n-1的无错奇圈中，以及偶数维折叠超立方体在至多有n-1个故障元的情况下，FQn中存在长为n+1到2n-2fv-1的无错奇圈。