### Long cycles in hypercubes with distant faulty vertices

*Petr Gregor, Riste Škrekovski*

#### Abstract

In this paper, we study long cycles in induced subgraphs of
hypercubes obtained by removing a given set of faulty vertices such
that every two faults are distant. First, we show that every induced
subgraph of Q

_{n}with minimum degree n-1 contains a cycle of length at least 2^{n}-2f where f is the number of removed vertices. This length is the best possible when all removed vertices are from the same bipartite class of Q_{n}. Next, we prove that every induced subgraph of Q_{n}obtained by removing vertices of some given set M of edges of Q_{n}contains a Hamiltonian cycle if every two edges of M are at distance at least 3. The last result shows that the shell of every linear code with odd minimum distance at least 3 contains a Hamiltonian cycle. In all these results we obtain significantly more tolerable faulty vertices than in the previously known results. We also conjecture that every induced subgraph of Q_{n}obtained by removing a balanced set of vertices with minimum distance at least 3 contains a Hamiltonian cycle.Full Text: PDF PostScript