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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2009, 11 (1), pp.185--198
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00988176
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 7 mai 2014 - 16:03:56
Dernière modification le : mercredi 29 novembre 2017 - 10:26:21
Document(s) archivé(s) le : jeudi 7 août 2014 - 11:30:55

Fichier

1005-4198-3-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

357

Téléchargements de fichiers

181