Structural and enumerative properties of the Fibonacci cubes (Q1849902)

The Fibonacci cube \(\Gamma_n\) of order \(n\) is the graph with vertices the binary \(n\)-strings without two consecutive 1's, connected whenever their Hamming (\(\ell_1\)) distance is 1. \(\Gamma_n\) is of order \(F_n\), the \(n\)th Fibonacci number, and is always bipartite, split between strings with even (\(E_n\)) and odd (\(O_n\)) component sum. Its radius is always \(\lceil n/2 \rceil\) with center the zero string for even \(n\), and additionally all strings with a single 1 and both 0-substrings even in case \(n\) is odd. Its independence number equals \(\max(e_n,o_n)\), where \(e_n=|E_n|\) and \(o_n=|O_n|\). For these last two values combined recurrence relations are determined, and it is shown that their difference follows a cyclic sequence of period \((1, 0, -1, -1, 0, 1)\). Finally new direct summation formulae for the Fibonacci numbers are obtained using this difference and binomials.