科研之友
微信
新浪微博
Facebook
分享链接
摘要
An important task in the theory of hypercubes is to establish the maximum integer f(n) such that for every set F of f vertices in the hypercube Q(n), with 0 <= f <= f(n), there exists a cycle of length at least 2(n) - 2f in the complement of F. 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) = (n2) - 2 for each n >= 4. New results regarding the existence of longest fault-free paths with prescribed ends are also proved.
- 出版日期2010-10
