Hamiltonian cycles passing through linear forests in k-ary n-cubes

详细信息    查看全文

• 作者：Shiying Wang^a ; ^{shiying@sxu.edu.cn"" rel=""nofollow} ; Yuxing Yang^b ; ^c ; ^{yxyangcn@163.com"" rel=""nofollow} ; Jing Li^a ; ^{jing-li83@hotmail.com"" rel=""nofollow} ; Shangwei Lin^a ; ^{shangweilin@sxu.edu.cn"" rel=""nofollow}
• 关键词：Interconnection networks ; ; none ; color ; black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-535DY4N-1&_mathId=mml15&_pii=S0166218X11001909&_issn=0166218X&_acct=C000050441&_version=1&_userid=1019048&md5
• 刊名：Discrete Applied Mathematics
• 出版年：2011
• 出版时间：28 August 2011
• 年：2011
• 卷：159
• 期：14
• 页码：1425-1435
• 全文大小：455 K

文摘

The k-ary n-cube is one of the most popular interconnection networks for parallel and distributed systems. A linear forest in a graph is a subgraph, each component of which is a path. In this paper, we investigate the existence of Hamiltonian cycles passing through linear forests in the k-ary n-cube. For any n≥2 and k≥3, we show that the k-ary n-cube admits a Hamiltonian cycle passing through a linear forest with at most 2n−1 edges.