容错变形超立方体的圈和路（英文）

Hamilton paths and cycles in fault-tolerant varietal hypercubes

考虑包含故障边的n(n≥3)维变形超立方体VQn,证明了:如果故障边数不超过n-2,那么VQn包含非故障边的Hamilton圈;如果故障边数不超过n-3,那么对任何两个不同顶点x和y,VQn包含非故障边的xy-Hamilton路.该证明方法采用归纳法.

The varietal hypercube VQn, a variant of the hypercube Qn, was studied. It was proved that VQn contains a fault-free Hamilton cycle provided faulty edges do not exceed n-2, and that for two distinct vertices, x and y, there is a fault-free xy-Hamilton path in VQ, provided faulty edges do not exceed n-3 for n≥3. The proof is based on an inductive construction.