On a Problem on Generalised Fibonacci Cubes

Abstract

A Fibonacci string of order $n$ is a binary string of length $n$ with no two consecutive ones. The Fibonacci cube ${\mathrm{\Gamma }}_n$ is the subgraph of the hypercube $Q_n$ induced by the set of Fibonacci strings of order $n$. For positive integers $i,n$, with $n\ge i$, the $i$th extended Fibonacci cube is the vertex-induced subgraph of $Q_n$ for which $V({\mathrm{\Gamma }}_i^n)=V_i$ is defined recursively by

$$V_{n+2}^i=0V_{n+1}^i+10V_n^i,$$

with initial conditions $V_i^i=B_i,V_{i+1}^i=B_{i+1}$, where $B_k$ denotes the set of binary strings of length $k$. In this study, we answer in the affirmative a conjecture of Wu [10] that the sequences $\{|V_n^i|{\}}_{i=1+2}^{\mathrm{\infty }}$ are pairwise disjoint for all $i\ge 0$, where $V_n^0=V({\mathrm{\Gamma }}_n)$.