超立方体中的路径嵌入

Embedding Paths into Hypercubes

研究了超立方体中任意两个不同顶点之间的路径嵌入问题,用构造法证明了结论在超立方体中,如果两个顶点之间的距离为奇数(偶数)并且被嵌入的路径的长度也是奇数(偶数),那么所有可能长度的路径都能以扩张1嵌入到两个顶点之间;如果两个顶点之间的距离是偶数(奇数)但被嵌入的路径的长度是奇数(偶数),那么所有可能奇(偶)长度的路径都不能以扩张1嵌入到两个顶点之间。该研究解决了超立方体中任意两顶点间所有可能长度的非容错路径嵌入问题。

In this paper, we study path embeddings between any two distinct nodes in hypercubes. By using constructive method, we prove the following results in the hypercube： Paths of all possible lengths can be embedded between any two nodes with dilation 1 if the lengths of the paths are odd （even） and the distance between the two nodes is also odd （even） ; Paths of all possible even （odd） lengths cannot be embedded between the two nodes with dilation 1, if the lengths of the paths are odd （even） but the distance between the two nodes is even （odd）. This research has solved the problem for fault-free embeddings of paths of all possible lengths in hypercubes.