Skip to Main content Skip to Navigation
Journal articles

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

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-01364442
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, September 12, 2016 - 3:50:59 PM
Last modification on : Thursday, September 7, 2017 - 1:03:45 AM
Long-term archiving on: : Tuesday, December 13, 2016 - 3:23:17 PM

File

2756-9997-1-PB.pdf
Explicit agreement for this submission

Identifiers

  • HAL Id : hal-01364442, version 1

Collections

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⟩

Share

Metrics

Record views

82

Files downloads

856