文摘
The generalized Fibonacci cube Qd(f) is the graph obtained from the hypercube Qd by removing all vertices that contain a given binary word f. A word f is called good if Qd(f) is an isometric subgraph of Qd for all d≥1, and bad otherwise. The index B(f) of a word f is the smallest integer d such that Qd(f) is not an isometric subgraph of Qd. 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 f is bad if there exist 03b4dd250426242c0a40f4360f3" title="Click to view the MathML source">p-critical words for Qd(f) for some d. 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 b4528c4ac2d979cd" title="Click to view the MathML source">QB(f)(f). We also design an O(|f|3) algorithm which can output the index B(f) of f, and give all pairs of 03b4dd250426242c0a40f4360f3" title="Click to view the MathML source">p-critical words for b4528c4ac2d979cd" title="Click to view the MathML source">QB(f)(f).