On the Conditional Edge Connectivity of Enhanced Hypercube Networks

Abstract

Let $G = (V, E)$ be a connected graph and $m$ be a positive integer, the conditional edge connectivity $\lambda^m_\delta$ is the minimum cardinality of a set of edges, if it exists, whose deletion disconnects $G$ and leaves each remaining component with minimum degree $\delta$ no less than $m.$ This study shows that $\lambda^1_\delta (Q_{n,k}) = 2n,$ $λ^2_\delta(Q_{n,k}) = 4n − 4$$(2 ≤ k ≤ n − 1, n ≥ 3)$ for $n$-dimensional enhanced hypercube $Q_{n,k}.$ Meanwhile, another easy proof about $\lambda^2_\delta (Q_n) = 4n − 8,$ for $n ≥ 3$ is proposed. The results of enhanced hypercube include the cases of folded hypercube.