Connectivity of Fibonacci cubes, Lucas cubes and generalized cubes

Abstract : If f is a binary word and d a positive integer, then the generalized Fibonacci cube Qd(f) is the graph obtained from the d-cube Qd by removing all the vertices that contain f as a factor, while the generalized Lucas cube Qd(lucas(f)) is the graph obtained from Qd by removing all the vertices that have a circulation containing f as a factor. The Fibonacci cube Γd and the Lucas cube Λd are the graphs Qd(11) and Qd(lucas(11)), respectively. It is proved that the connectivity and the edge-connectivity of Γd as well as of Λd are equal to ⌊ d+2 / 3⌋. Connected generalized Lucas cubes are characterized and generalized Fibonacci cubes are proved to be 2-connected. It is asked whether the connectivity equals minimum degree also for all generalized Fibonacci/Lucas cubes. It was checked by computer that the answer is positive for all f and all d≤9.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (in progress) (1), pp.79--88
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01196859
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 10 septembre 2015 - 15:17:22
Dernière modification le : jeudi 7 septembre 2017 - 01:03:42
Document(s) archivé(s) le : mardi 29 décembre 2015 - 00:02:17

Fichier

dmtcs-17-1-5.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01196859, version 1

Collections

Citation

Jernej Azarija, Sandi Klavžar, Jaehun Lee, Yoomi Rho. Connectivity of Fibonacci cubes, Lucas cubes and generalized cubes. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (in progress) (1), pp.79--88. 〈hal-01196859〉

Partager

Métriques

Consultations de la notice

110

Téléchargements de fichiers

258