Discrete Mathematics & Theoretical Computer Science, Vol 11, No 1 (2009)

Font Size:  Small  Medium  Large

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 Qn with minimum degree n-1 contains a cycle of length at least 2n-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 Qn. Next, we prove that every induced subgraph of Qn obtained by removing vertices of some given set M of edges of Qn 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 Qn obtained by removing a balanced set of vertices with minimum distance at least 3 contains a Hamiltonian cycle.

Full Text: PDF PostScript