Structural and enumerative properties of the Fibonacci cubes

DOI10.1016/S0012-365X(01)00407-1MaRDI QIDQ1849902zbMATH OpenOpenAlexFDO

Authors Emanuele Munarini, Norma Zagaglia Salvi

Publication date 2 December 2002

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(01)00407-1

zbMATH Keywords

bipartite graphFibonacci cubesFibonacci numbers

Mathematics Subject Classification ID

Distance in graphs (05C12) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

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.

Recommendations

• Structure of Fibonacci cubes: a survey
• Fibonacci and Lucas \(p\)-cubes
• The Fibonacci hypercube
• The degree sequence of Fibonacci and Lucas cubes
• The eccentricity sequences of Fibonacci and Lucas cubes

Cited in

(37)

• Fibonacci-like cubes as \(Z\)-transformation graphs
• Observability of the extended Fibonacci cubes
• Structure of Fibonacci cubes: a survey
• Fibonacci and Lucas \(p\)-cubes
• The radius and center of Fibonacci-run graphs
• Enumerative properties and cube polynomials of Tribonacci cubes
• The degree sequence of Fibonacci and Lucas cubes
• Determining which Fibonacci (\(p,r\))-cubes can be \(Z\)-transformation graphs
• Pell graphs
• On disjoint hypercubes in Fibonacci cubes
• All good (bad) words consisting of 5 blocks
• Fast recognition of Fibonacci cubes
• \(\Theta\)-graceful labelings of partial cubes
• Recursive fault-tolerance of Fibonacci cube in hypercubes
• On median nature and enumerative properties of Fibonacci-like cubes
• The domination number of Fibonacci cubes
• Asymptotic properties of Fibonacci cubes and Lucas cubes
• Proofs of two conjectures on generalized Fibonacci cubes
• Generalized Fibonacci and Lucas cubes arising from powers of paths and cycles
• Decycling bipartite graphs
• Some diameter notions of Fibonacci cubes
• scientific article; zbMATH DE number 2197928 (Why is no real title available?)
• k-Fibonacci cubes: a family of subgraphs of Fibonacci cubes
• Hypercubes and isometric words based on swap and mismatch distance
• Metallic cubes
• On the domination number and the 2-packing number of Fibonacci cubes and Lucas cubes
• Asymptotic number of isometric generalized Fibonacci cubes
• Generalized Fibonacci cubes
• Cube polynomial of Fibonacci and Lucas cubes
• Partitions with fixed largest hook length
• Horadam cubes
• Metallic cubes are the resonance graphs of phenylenes
• Mutual and total mutual visibility in hypercube-like graphs
• On a conjecture of Eǧecioǧlu and Iršič
• Isometric sets of words and generalizations of the Fibonacci cubes
• Maximal hypercubes in Fibonacci and Lucas cubes
• The eccentricity sequences of Fibonacci and Lucas cubes

This page was built for publication: Structural and enumerative properties of the Fibonacci cubes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1849902)