Embedded paths and cycles in faulty hypercubes (Q5893937)

If \(f\) ``faulty'' vertices of the same parity are deleted from the \(n\)-dimensional binary hypercube \(\mathcal{Q}_{n}\), the length of the longest fault-free cycle cannot exceed \(2^{n}-2f\). A natural question is to determine the maximum integer \(f_{n}\) such that for every set \(\mathcal{F}\) of \(f\) deleted vertices with \(0 \leq f \leq f_{n}\) there exists a cycle of length at least \(2^{n}-2f\) in the complement of \(\mathcal{F}\). In [\textit{J.-S. Fu}, Parallel Comput. 29, 821--832 (2003; Zbl 1243.68030)], exact values of \(f_{n}\) have been given for \(n \leq 4\) together with a lower bound of \(2n-4\) for \(n \geq 5\). In this paper the authors show that \(f_{5}=8\) and that \(3n-7\) is a lower bound on \(f_{n}\) for all \(n \geq 5\). Their results motivate the following conjecture: Let \(n \geq 4\) and \(f\) be integers with \(0 \leq f \leq \binom{n}{2}-2\). Then for any set \(\mathcal{F}\) of vertices in \(\mathcal{Q}_{n}\) of cardinality \(f\) there exists a cycle in \(\mathcal{Q}_{n}-\mathcal{F}\) of length at least \(2^{n}-2f\). Some results on the existence of longest fault-free paths with prescribed ends are also presented.