Proofs of two conjectures on generalized Fibonacci cubes

Jianxin Wei; Heping Zhang

paper

Proofs of two conjectures on generalized Fibonacci cubes

arXiv:1501.00378

Abstract

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 \geq 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}$ . Ilić, 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 the two conjectures by obtaining a basic result: if there exist $p$ -critical words for $Q_{B (f)} (f)$ , then $p$ =2 or $p = 3$ .