Linear recognition of generalized Fibonacci cubes $Q_h (111)$Rho, Yoomi (Avtor) Vesel, Aleksander (Avtor) graph theoryFibonacci cubesrecognition algorithmThe 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. Discrete Mathematics & Theoretical Computer Science20162017-07-10 11:40:59Znanstveno delo66782sl