Long cycles in hypercubes with optimal number of faulty vertices

Jiří Fink () and Petr Gregor ()
Additional contact information
Jiří Fink: Charles University in Prague
Petr Gregor: Charles University in Prague

Journal of Combinatorial Optimization, 2012, vol. 24, issue 3, No 7, 240-265

Abstract: Abstract 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. Castañeda and Gotchev conjectured that $f(n)=\binom{n}{2}-2$ . 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.

Keywords: Hypercube; Faulty vertices; Long cycle (search for similar items in EconPapers)
Date: 2012
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-011-9379-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:24:y:2012:i:3:d:10.1007_s10878-011-9379-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-011-9379-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().