The Fibonacci cube graph of order is a graph on vertices, where is a Fibonacci number,
labeled by the Zeckendorf representations
of the numbers 0 to
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 may be denoted (Munarini et al. 2001, Munarini 2019). is also the simplex graph
of the path complement graph (Alikhani and Ghanbari 2024).
Fibonacci cube graphs are traceable and bipartite. The -Fibonacci
cube graph is Hamiltonian for , 7, 10, .... The Fibonacci cube graphs are also median
graphs (Klavar 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).
Alikhani, S. and Ghanbari, N. "Golden Ratio in Graph Theory: A Survey." 9 Jul 2024. https://arxiv.org/abs/2407.15860.Castro,
A.; Klavar, 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 Systems4, 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.Klavar, S. "On
Median Nature and Enumerative Properties of Fibonacci-Like Cubes." Disc.
Math.299, 145-153, 2005.Klavar, S. and Mollard, M.
"Wiener Index and Hosoya Polynomial of Fibonacci and Lucas Cubes." MATCH
Commun. Math. Comput. Chem.68, 311-324, 2012.Klavar,
S. and Mollard, M. "Asymptotic Properties of Fibonacci Cubes and Lucas Cubes."
Ann. Combin.18, 447-457, 2014.Klavar, 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." Algorithmica49, 81-93, 2007.