Proofs of two conjectures on generalized Fibonacci cubes

A binary string f is a factor of string u if f appears as a sequence of | f | consecutive bits of u , where | f | denotes the length of f . Generalized Fibonacci cube Q d ( f ) is the graph obtained from the d -cube Q d by removing all vertices that contain a given binary string f as a factor. A binary string f is called good if Q d ( f ) is an isometric subgraph of Q d for all d ? 1 , it is called bad otherwise. The index of a binary string f , denoted by B ( f ) , is the smallest integer d such that Q d ( f ) is not an isometric subgraph of Q d . Ilic, Klav?ar and Rho conjectured that B ( f ) < 2 | f | for any bad string f . They also conjectured that if Q d ( f ) is an isometric subgraph of Q d , then Q d ( f f ) is an isometric subgraph of Q d . We confirm these two conjectures by obtaining a basic result: if there exist p -critical words for Q B ( f ) ( f ) , then p = 2 or p = 3 .