Yoomi Rho (Author), Aleksander Vesel (Author)

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 ... 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

teorija grafov;Fibonaccijeve kocke;algoritem prepoznavanja;graph theory;Fibonacci cubes;recognition algorithm;

Data

Language: English
Year of publishing:
Typology: 1.01 - Original Scientific Article
Organization: UM FNM - Faculty of Natural Sciences and Mathematics
UDC: 519.17
COBISS: 22599944 Link will open in a new window
ISSN: 1365-8050
Views: 754
Downloads: 135
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: Slovenian
Secondary keywords: teorija grafov;Fibonaccijeve kocke;algoritem prepoznavanja;
URN: URN:SI:UM:
Type (COBISS): Scientific work
Pages: str. 349-362
Volume: ǂVol. ǂ17
Issue: ǂno. ǂ3
Chronology: 2016
ID: 10847395