Abstract
An important task in the theory of hypercubes is to establish the maximum integer f n such that for every set ℱ of f vertices in the hypercube \({\mathcal {Q}}_{n},\) with 0≤f≤f n , there exists a cycle of length at least 2n−2f in the complement of ℱ. Until recently, exact values of f n were known only for n≤4, and the best lower bound available for f n with n≥5 was 2n−4. We prove that f 5=8 and obtain the lower bound f n ≥3n−7 for all n≥5. Our results and an example provided in the paper support the conjecture that \(f_{n}={n\choose 2}-2\) for each n≥4. New results regarding the existence of longest fault-free paths with prescribed ends are also proved.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Castañeda N, Gotchev IS (2007) Path coverings with prescribed ends in faulty hypercubes (submitted for publication)
Castañeda N, Gotchev IS (2008) On the hamiltonianicity of the hypercube with some deleted vertices. Preprint
Diestel R (2006) Graph theory, 3rd edn. Springer, Berlin
Dvořák T (2005) Hamiltonian cycles with prescribed edges in hypercubes. SIAM J Discrete Math 19:135–144
Dvořák T, Gregor P (2007) Hamiltonian paths with prescribed edges in hypercubes. Discrete Math 307:1982–1998
Fu J-S (2003) Fault-tolerant cycle embedding in the hypercube. Parallel Comput 29:821–832
Fu J-S (2006) Longest fault-free paths in hypercubes with vertex faults. Inf Sci 176:759–771
Havel I (1984) On Hamiltonian circuits and spanning trees of hypercubes. Čas Pěst Mat 109:135–152
Lewinter M, Widulski W (1997) Hyper-Hamilton laceable and caterpillar-spannable product graphs. Comput Math Appl 34(11):99–104
Locke SC (2001) Problem 10892. Am Math Mon 108:668
Locke SC, Stong R (2003) Spanning cycles in hypercubes. Am Math Mon 110:440–441
Tseng YC (1996) Embedding a ring in a hypercube with both faulty links and faulty nodes. Inf Process Lett 59:217–222
Yang PJ, Tien SB, Raghavendra CS (1994) Embedding of rings and meshes onto faulty hypercubes using free dimensions. IEEE Trans Comput 43:608–613
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Castañeda, N., Gotchev, I.S. Embedded paths and cycles in faulty hypercubes. J Comb Optim 20, 224–248 (2010). https://doi.org/10.1007/s10878-008-9205-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-008-9205-6