Charles Explorer logo
🇨🇿

Long cycles in hypercubes with optimal number of faulty vertices

Publikace na Matematicko-fyzikální fakulta |
2012

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

We prove a conjecture of Castaneda and Gotchev that for every set F of at most n(n-1)/2 vertices, the hypercube of dimension n contains a cycle of length at least 2^n-2|F| that avoids F. We also prove that for every set F of at most (n^2+n-4)/4 vertices, the hypercube of dimension n contains a path of length at least 2n-2|F|-2 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.