# Linear recognition of generalized Fibonacci cubes $Q_h(111)$

Abstract : The generalized Fibonacci cube $Q_h(f)$ is the graph obtained from the $h$-cube $Q_h$ by removing all vertices that contain a given binary string $f$ as a substring. In particular, the vertex set of the 3rd order generalized Fibonacci cube $Q_h(111)$ is the set of all binary strings $b_1b_2 \ldots b_h$ containing no three consecutive 1's. We present a new characterization of the 3rd order generalized Fibonacci cubes based on their recursive structure. The characterization is the basis for an algorithm which recognizes these graphs in linear time.
Keywords :
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.349-362

Littérature citée [17 références]

https://hal.inria.fr/hal-01364442
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 12 septembre 2016 - 15:50:59
Dernière modification le : jeudi 7 septembre 2017 - 01:03:45
Document(s) archivé(s) le : mardi 13 décembre 2016 - 15:23:17

### Fichier

2756-9997-1-PB.pdf
Accord explicite pour ce dépôt

### Identifiants

• HAL Id : hal-01364442, version 1

### Citation

Yoomi Rho, Aleksander Vesel. Linear recognition of generalized Fibonacci cubes $Q_h(111)$. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.349-362. 〈hal-01364442〉

### Métriques

Consultations de la notice

## 36

Téléchargements de fichiers