TOPICS
Search

Fibonacci Cube Graph


FibonacciCubeGraph

The Fibonacci cube graph F_n of order 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 of order 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 of order n has edge count

m(F_n)=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 higher-order Fibonacci numbers (Hsu and Chung 1993, Došlić and Podrug 2023).

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.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. 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. "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. and Salvi, N. Z. "Structural and Enumerative Properties of the Fibonacci Cubes." Disc. Math. 255, 317-324, 2022.Munarini, E.; Cippo, C. P.; and Salvi, N. Z. "On the Lucas Cubes." Fibonacci Quart. 39, 12-21, 2001.Taranenko, A. and Vesel, A. "Fast Recognition of Fibonacci Cubes." Algorithmica 49, 81-93, 2007.

Cite this as:

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

Subject classifications