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


Cycles passing through a prescribed path in a hypercube with faulty edges
Authors:Xie-Bin Chen
Affiliation:Department of Mathematics and Information Science, Zhangzhou Teachers College, Zhangzhou, Fujian 363000, China
Abstract:Let Qn denote an n-dimensional hypercube with n?2, P be a path of length h in Qn and FE(Qn)E(P). Recently, Tsai proved that if 1?h?n−1 and |F|?n−1−h, then in the graph QnF the path P lies on a cycle of every even length from 2h+2 to n2, and P also lies on a cycle of length 2h if |F|?h−2. In this paper, we show that if 1?h?2n−3 and |F|?n−2−⌊h/2⌋, then in QnF the path P lies on a cycle of every even length from 2h+2 to n2, and P also lies on a cycle of length 2h if P contains two edges of the same dimension or P is a shortest path and |FE(Qh)|?h−2, where Qh is the h-dimensional subcube containing the path P. Moreover, the upper bound 2n−3 of h is sharp and the upper bound n−2−⌊h/2⌋ of |F| is sharp for any given h with 1?h?2n−3.
Keywords:Hypercube   Cycle embedding   Path bipancyclicity   Edge-fault-tolerance   Interconnection networks
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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