Embedded paths and cycles in faulty hypercubes |
| |
Authors: | Nelson Castañeda Ivan S Gotchev |
| |
Institution: | 1.Department of Mathematical Sciences,Central Connecticut State University,New Britain,USA |
| |
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
Qn,{\mathcal {Q}}_{n},
with 0≤f≤f
n
, there exists a cycle of length at least 2
n
−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
fn=((n) || 2)-2f_{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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|