Skip to Main content Skip to Navigation
Journal articles

Long cycles in hypercubes with distant faulty vertices

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) - 2(f) 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/hal-00988176
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Wednesday, May 7, 2014 - 4:03:56 PM
Last modification on : Friday, March 15, 2019 - 4:55:06 PM
Long-term archiving on: : Thursday, August 7, 2014 - 11:30:55 AM

File

1005-4198-3-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00988176, version 1

Collections

Citation

Petr Gregor, Riste Škrekovski. Long cycles in hypercubes with distant faulty vertices. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2009, 11 (1), pp.185--198. ⟨hal-00988176⟩

Share

Metrics

Record views

425

Files downloads

818