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