科研之友
微信
新浪微博
Facebook
分享链接
摘要
Let f(n) be the maximum integer such that for every set F of at most f(n) vertices of the hypercube Q (n) , there exists a cycle of length at least 2 (n) -2|F| in Q (n) -F. Castaeda and Gotchev conjectured that . We prove this conjecture. We also prove that for every set F of at most (n (2)+n-4)/4 vertices of Q (n) , there exists a path of length at least 2 (n) -2|F|-2 in Q (n) -F between any two vertices such that each of them has at most 3 neighbors in F. We introduce a new technique of potentials which could be of independent interest.
- 出版日期2012-10
