Vertex-Fault-Tolerant Cycles Embedding in Four-Conditionally Faulty Enhanced Hypercube Networks

Abstract

In a network G, if each vertex of G is incident to at least $g \, (\geq 1)$ fault-free vertices, then we say the network is g-conditionally faulty. An enhanced hypercube $Q_{n,k}$ is a network, which is an attractive variant of the hypercube $Q_{n}$ by adding complementary edges between any vertices with the complementary addresses. Let $F_{v}^{*}$ be the set of faulty vertices in $Q_{n,k}$ . In this paper, in the 4-conditionally faulty $Q_{n,k}$ , we show that $Q_{n,k}-F_{v}^{*}$ contains a fault-free even cycle ranging in length from 4 to $2^{n}-2|F_{v}^{*}|$ , where $n\geq 3$ and $|F_{v}^{*}|\leq 2n-4$ ; and also contains a fault-free odd cycle ranging in length from $n-k+2$ to $2^{n}-2|F_{v}^{*}|-1$ , where $n \, (\geq 3)$ , $2\nmid (n-k)$ and $|F_{v}^{*}|\leq 2n-5$ .

Keywords

• Cycles embedding
• enhanced hypercube
• conditionally faulty model
• interconnection network