Edge-fault-tolerant diameter and bipanconnectivity of hypercubes

Let n(⩾3)n(⩾3) be a given integer and Ωk={l|k⩽l⩽2n−1andl−kis even}. And let QnQn be an n  -dimensional hypercube and F⊂E(Qn)F⊂E(Qn), such that every vertex of the graph Qn−FQn−F is incident with at least two edges. Assume x and y   are any two vertices with Hamming distance H(x,y)=hH(x,y)=h. In this paper, we obtain the following results: (1) If h⩾2h⩾2 and |F|⩽min{n+h−1,2n−5}|F|⩽min{n+h−1,2n−5}, then in Qn−FQn−F there exists an xy  -path of each length l∈Ωh+2l∈Ωh+2, and the upper bound n+h−1n+h−1 on |F||F| is sharp when 2⩽h⩽n−42⩽h⩽n−4, and the upper bound 2n−52n−5 on |F||F| is sharp when n−4⩽h⩽n−1n−4⩽h⩽n−1 and h=2h=2. (2) If |F|⩽2n−5|F|⩽2n−5, then in Qn−FQn−F there exists an xy  -path of each length l∈Ωsl∈Ωs, where s=hs=h if n−1⩽h⩽nn−1⩽h⩽n, and s=h+2s=h+2 if n−4⩽h⩽n−2n−4⩽h⩽n−2 and h⩾2h⩾2, and s=h+4s=h+4 otherwise. Hence, the diameter of the graph Qn−FQn−F is n. Our results improve some previous results.

Research highlights► Edge-fault-tolerant diameter of the hypercube is determined. ► The previous results on edge-fault-tolerant bipanconnectivity of the hypercube are improved.