The structures of bad words

The generalized Fibonacci cube Qd(f)Qd(f) is the graph obtained from the hypercube QdQd by removing all vertices that contain a given binary word ff. A word ff is called good if Qd(f)Qd(f) is an isometric subgraph of QdQd for all d≥1d≥1, and bad otherwise. The index B(f)B(f) of a word ff is the smallest integer dd such that Qd(f)Qd(f) is not an isometric subgraph of QdQd. Klavžar and Shpectorov showed that a bad word has a 2-error overlap. In this paper, we show that if a word has a 2-error overlap then it is bad, and we characterize the structures of all bad words. Ilić, Klavžar and Rho showed that a word ff is bad if there exist pp-critical words for Qd(f)Qd(f) for some dd. We find that a word is bad if and only if there exists only a pair of 2-critical words, or only a pair of 3-critical words, or both only a pair of 2-critical words and only a pair of 3-critical words for QB(f)(f)QB(f)(f). We also design an O(|f|3)O(|f|3) algorithm which can output the index B(f)B(f) of ff, and give all pairs of pp-critical words for QB(f)(f)QB(f)(f).