首页 | 本学科首页   官方微博 | 高级检索  
     


Embedding hamiltonian paths in hypercubes with a required vertex in a fixed position
Authors:Chung-Meng Lee  Lih-Hsing Hsu
Affiliation:a Department of Computer Science, National Chiao Tung University, Hsinchu, Taiwan 30010, ROC
b Department of Computer Science and Information Engineering, Providence University, Taiwan, ROC
Abstract:Assume that n is a positive integer with n?2. It is proved that between any two different vertices x and y of Qn there exists a path Pl(x,y) of length l for any l with h(x,y)?l?n2−1 and 2|(lh(x,y)). We expect such path Pl(x,y) can be further extended by including the vertices not in Pl(x,y) into a hamiltonian path from x to a fixed vertex z or a hamiltonian cycle. In this paper, we prove that for any two vertices x and z from different partite set of n-dimensional hypercube Qn, for any vertex yV(Qn)−{x,z}, and for any integer l with h(x,y)?l?n2−1−h(y,z) and 2|(lh(x,y)), there exists a hamiltonian path R(x,y,z;l) from x to z such that dR(x,y,z;l)(x,y)=l. Moreover, for any two distinct vertices x and y of Qn and for any integer l with h(x,y)?l?2n−1 and 2|(lh(x,y)), there exists a hamiltonian cycle S(x,y;l) such that dS(x,y;l)(x,y)=l.
Keywords:Interconnection networks
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号