TOPICS
Search

Fibonacci Cube Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
FibonacciCubeGraph

The Fibonacci cube graph F_n with index n is a graph on F_(n+2) vertices, where F_n is a Fibonacci number, labeled by the Zeckendorf representations of the numbers 0 to F_(n+2)-1 and with two vertices connected by an edge iff their labels differ by a single bit (i.e., if the Hamming distance between them is exactly 1). The Fibonacci cube with index n may be denoted Gamma_n (Munarini et al. 2001, Munarini 2019). F_n is also the simplex graph of the path complement graph P^__n (Alikhani and Ghanbari 2024).

The Fibonacci cube graph with index n has edge count

m(F_n)=1/5[2(n+1)F_n+nF_(n+1)]
(1)
=1/(10)[(5n+4)F_n+nL_n],
(2)

where F_n is a Fibonacci number and L_n is a Lucas number.

Fibonacci cube graphs are traceable and bipartite. The n-Fibonacci cube graph is Hamiltonian for n=4, 7, 10, .... The Fibonacci cube graphs are also median graphs (Klavžar 2005, Došlić and Podrug 2023).

Fibonacci cubes have been generalized to graphs having vertex counts counted by various types of generalized Fibonacci numbers (Hsu and Chung 1993, Došlić and Podrug 2023).

Precomputed properties of Fibonacci cube graphs are implemented in the Wolfram Language as GraphData[{"FibonacciCube", n}].

Special cases are summarized in the table below.

ngraph
1path graph P_2
2path graph P_3
3banner graph
4L-triomino graph

See also

Fibonacci Number, Hypercube Graph, Lucas Cube Graph, Pell Graph, Zeckendorf Representation

Explore with Wolfram|Alpha

References

Alikhani, S. and Ghanbari, N. "Golden Ratio in Graph Theory: A Survey." 9 Jul 2024. https://arxiv.org/abs/2407.15860.Castro, A.; Klavžar, S.; Mollard, M.; and Rho, T. "On the Domination Number and the 2-Packing Number of Fibonacci Cubes and Lucas Cubes." Comput. Math. Appl. 61, 2655-2660, 2011.Castro, A. and Mollard, M. "The Eccentricity Sequences of Fibonacci and Lucas Cubes." Disc. Math. 312, 1025-1037, 2012.Dedò, E.; Torri, D.; and Salvi, N. Z. "The Observability of the Fibonacci and the Lucas Cubes." Disc. Math. 255, 55-63, 2002.Došlić, T. and Podrug, L. "Metallic Cubes." 26 Jul 2023. https://arxiv.org/abs/2307.14054.House of Graphs. Fibonacci Cube Graphs. Banner Graph, K2, and Path Graph P3.Hsu, W. J. "Fibonacci Cubes: A New Class of Interconnection Topologies for Parallel Processing." IEEE Trans. Parallel and Distributed Systems 4, 3-12, 1993.Hsu, W. J. and Chung, M. J. "Generalized Fibonacci Cubes." Proc. Internat. Conf. Parallel Processing (1993), 299-303, 1993.Hsu, W.-J.; Page, C. V.; and Liu, J.-S. "Fibonacci Cubes: A Class of Self-Similar Graphs." Fib. Quart. 31, 65-72, 1993.Ilić, A. and Milošević, M. "The Parameters of Fibonacci and Lucas Cubes." Ars Math. Contemp. 12, 25-29, 2017.Klavžar, S. "On Median Nature and Enumerative Properties of Fibonacci-Like Cubes." Disc. Math. 299, 145-153, 2005.Klavžar, S. "Structure of Fibonacci Cubes: A Survey" J. Combin. Opt. 25, 505-522, 2013.Klavžar, S. and Mollard, M. "Wiener Index and Hosoya Polynomial of Fibonacci and Lucas Cubes." MATCH Commun. Math. Comput. Chem. 68, 311-324, 2012.Klavžar, S. and Mollard, M. "Cube Polynomial of Fibonacci and Lucas Cubes." Acta Appl. Math. 117, 93-105, 2012.Klavžar, S. and Mollard, M. "Asymptotic Properties of Fibonacci Cubes and Lucas Cubes." Ann. Combin. 18, 447-457, 2014.Klavžar, S.; Mollard, M.; and Petkovšek, M. "The Degree Sequence of Fibonacci and Lucas Cubes." Disc. Math. 311, 1310-1322, 2001.Munarini, E. "Pell Graphs." Disc. Math. 342, 2415-2428, 2019.Munarini, E.; Cippo, C. P.; and Salvi, N. Z. "On the Lucas Cubes." Fibonacci Quart. 39, 12-21, 2001.Munarini, E. and Salvi, N. Z. "Structural and Enumerative Properties of the Fibonacci Cubes." Disc. Math. 255, 317-324, 2022.Taranenko, A. and Vesel, A. "Fast Recognition of Fibonacci Cubes." Algorithmica 49, 81-93, 2007.

Referenced on Wolfram|Alpha

Fibonacci Cube Graph

Cite this as:

Weisstein, Eric W. "Fibonacci Cube Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/FibonacciCubeGraph.html

Subject classifications