Discrete Mathematics & Theoretical Computer Science, Vol 17, No 3 (2016)

Font Size:  Small  Medium  Large

Linear recognition of generalized Fibonacci cubes Qh(111)

Yoomi Rho, Aleksander Vesel


The generalized Fibonacci cube Qh(f) is the graph obtained from the h-cube Qh 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 Qh(111) is the set of all binary strings b1b2 …bh 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