Structural and enumerative properties of the Fibonacci cubes
type: Item
instance of: scholarly article
title: Structural and enumerative properties of the Fibonacci cubes
zbMATH Open document ID: 1008.05048
DOI: 10.1016/S0012-365X(01)00407-1
author: Emanuele Munarini
author: Norma Zagaglia Salvi
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: 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.
reviewed by: Frank Plastria
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 11B39
zbMATH DE Number: 1838900
zbMATH Keywords: Fibonacci numbers
zbMATH Keywords: Fibonacci cubes
zbMATH Keywords: bipartite graph
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00407-1
OpenAlex ID: W1996538498
description: scientific article; zbMATH DE number 1838900