Edge-fault-tolerant diameter and bipanconnectivity of hypercubes |
| |
Authors: | Xie-Bin Chen |
| |
Affiliation: | Department of Mathematics and Information Science, Zhangzhou Teachers College, Zhangzhou, Fujian 363000, China |
| |
Abstract: | Let n(?3) be a given integer and . And let Qn be an n-dimensional hypercube and F⊂E(Qn), such that every vertex of the graph Qn−F is incident with at least two edges. Assume x and y are any two vertices with Hamming distance H(x,y)=h. In this paper, we obtain the following results: (1) If h?2 and |F|?min{n+h−1,2n−5}, then in Qn−F there exists an xy-path of each length l∈Ωh+2, and the upper bound n+h−1 on |F| is sharp when 2?h?n−4, and the upper bound 2n−5 on |F| is sharp when n−4?h?n−1 and h=2. (2) If |F|?2n−5, then in Qn−F there exists an xy-path of each length l∈Ωs, where s=h if n−1?h?n, and s=h+2 if n−4?h?n−2 and h?2, and s=h+4 otherwise. Hence, the diameter of the graph Qn−F is n. Our results improve some previous results. |
| |
Keywords: | Hypercube Path embedding Bipanconnectivity Fault tolerance Fault-tolerant diameter Interconnection networks |
本文献已被 ScienceDirect 等数据库收录! |
|