### Linear recognition of generalized Fibonacci cubes Q_{h}(111)

*Yoomi Rho, Aleksander Vesel*

#### 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_{1}b_{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.Full Text: PDF