2015/04/03 by Sylvain Gravier, Gravier, Sylvain, Michel Mollard +5
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems #graph theory and CDMA systems
paper · doi:10.48550/arxiv.1504.00829
openalex publication_date 2015/04/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The \em Fibonacci cube of dimension n, denoted as Γ_n, is the subgraph of n-cube Q_n induced by vertices with no consecutive 1's. We study the maximum number of disjoint subgraphs in Γ_n isomorphic to Q_k, and denote this number by q_k(n). We prove several recursive results for q_k(n), in particular we prove that q_k(n) = q_k-1(n-2) + q_k(n-3). We also prove a closed formula in which q_k(n) is given in terms of Fibonacci numbers, and finally we give the generating function for the sequence \q_k(n)\_n=0 ∞.