Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6424090 | European Journal of Combinatorics | 2016 | 14 Pages |
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 Qd(f) is the graph obtained from the d-cube Qd by removing all vertices that contain a given binary string f as a factor. A binary string f is called good if Qd(f) is an isometric subgraph of Qd 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 Qd(f) is not an isometric subgraph of Qd. IliÄ, Klavžar and Rho conjectured that B(f)<2|f| for any bad string f. They also conjectured that if Qd(f) is an isometric subgraph of Qd, then Qd(ff) is an isometric subgraph of Qd. We confirm these two conjectures by obtaining a basic result: if there exist p-critical words for QB(f)(f), then p=2 or p=3.