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 F⊂E(Qn)E(P). Recently, Tsai proved that if 1?h?n−1 and |F|?n−1−h, then in the graph Qn−F 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 Qn−F 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 |F∩E(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 等数据库收录! |
|