Embedded paths and cycles in faulty hypercubes
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.
- Long paths and cycles in faulty hypercubes: existence, optimality, complexity
- Long paths and cycles in hypercubes with faulty vertices
- Edge-fault-tolerant properties of hypercubes and folded hypercubes
- Fault-tolerant cycles embedded in hypercubes with mixed link and node failures
- Cycles embedding in hypercubes with node failures
- Computational complexity of long paths and cycles in faulty hypercubes
- A note on cycle embedding in hypercubes with faulty vertices
- Linear array and ring embeddings in conditional faulty hypercubes
- Fault-free cycles passing through prescribed paths in hypercubes with faulty edges
- Edge-fault-tolerant bipanconnectivity of hypercubes
- Embedding a ring in a hypercube with both faulty links and faulty nodes
- Fault-tolerant cycle embedding in the hypercube
- Graph theory
- Hamiltonian Cycles with Prescribed Edges in Hypercubes
- Hamiltonian paths with prescribed edges in hypercubes
- Hyper-Hamilton laceable and caterpillar-spannable product graphs
- Longest fault-free paths in hypercubes with vertex faults
- On Hamiltonian circuits and spanning trees of hypercubes
- Hamiltonian laceability in hypercubes with faulty edges
- Long cycles in hypercubes with optimal number of faulty vertices
- Path coverings with prescribed ends in faulty hypercubes
- On the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty hypercube
- Construction of maximum cycles in faulty binary hypercubes
- Long cycles in hypercubes with distant faulty vertices
- Paths and cycles embedding on faulty enhanced hypercube networks
- scientific article; zbMATH DE number 17938 (Why is no real title available?)
- Gray codes with bounded weights
- SOME RESULTS ON BUDS, STEMS AND FAULT TOLERANCE IN HYPERCUBES OF DIMENSION ⋚ 5
- scientific article; zbMATH DE number 6263048 (Why is no real title available?)
- Long paths and cycles in faulty hypercubes: existence, optimality, complexity
- Matchings in hypercubes extend to long cycles
- Matchings in hypercubes extend to long cycles
- Computational complexity of long paths and cycles in faulty hypercubes
- Long paths and cycles in hypercubes with faulty vertices
- Long paths in hypercubes with a quadratic number of faults
- Cycles passing through a prescribed path in a hypercube with faulty edges
- Hybrid fault-tolerant prescribed hyper-Hamiltonian laceability of hypercubes
- Fault-tolerant embedding of paths in crossed cubes
- Path embedding in faulty hypercubes
This page was built for publication: Embedded paths and cycles in faulty hypercubes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5893937)
