# Fibonacci cube
The **Fibonacci cube** Γ_n is the subgraph of the n-dimensional hypercube Q_n induced by the binary strings of length n that contain no two consecutive 1s, with two vertices adjacent when they differ in exactly one bit.[1](https://www.sciencedirect.com/science/article/pii/S0012365X05002748) It was introduced by Wen-Ping Hsu in 1993 as an interconnection topology with hypercube-like recursive structure on a vertex set whose size is not a power of two.[2](https://users.fmf.uni-lj.si/klavzar/preprints/FibonacciCubesRevised.pdf) The excluded vertices are exactly those containing the substring 11, so Γ_n is also written Q_n(11) in the notation of generalized [Fibonacci](https://www.edgepedia.org/fibonacci) cubes.[3](https://users.fmf.uni-lj.si/klavzar/preprints/GFC-revised.pdf)
| Key fact | Detail |
|---|---|
| Vertices | The F_{n+2} Fibonacci strings of length n; Γ_1 = K_2 and Γ_2 is the path on three vertices[2](https://users.fmf.uni-lj.si/klavzar/preprints/FibonacciCubesRevised.pdf) • [4](https://ar5iv.labs.arxiv.org/html/1306.5154) |
| Edges | \( |E(\Gamma_n)| = (nF_{n+1} + 2(n+1)F_n)/5 \)[4](https://ar5iv.labs.arxiv.org/html/1306.5154) |
| Embedding | A median graph, hence a partial cube isometrically embedded in Q_n[5](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v18i1p55/pdf) |
| Diameter and radius | Diameter n (Hsu, 1993); radius ⌈n/2⌉[6](https://www.fq.math.ca/Scanned/31-1/hsu.pdf) • [2](https://users.fmf.uni-lj.si/klavzar/preprints/FibonacciCubesRevised.pdf) |
| Decomposition | Γ_n = 0Γ_{n−1} + 10Γ_{n−2}: vertices starting with 0 form a Γ_{n−1}, vertices starting with 10 form a Γ_{n−2}[7](https://cs.ucsb.edu/sites/default/files/documents/k-fibonacci_cubes_egecioglu_saygi_nov29_2019.pdf) |
| Chemistry | Γ_n is the resonance graph of every fibonacene with n hexagons[2](https://users.fmf.uni-lj.si/klavzar/preprints/FibonacciCubesRevised.pdf) |
| Connectivity | Diameter, edge connectivity, and node connectivity are logarithmic in the number N of nodes[8](https://dl.acm.org/doi/10.1109/71.205649) |
## Definition and first examples
A **Fibonacci string** of length n is a binary string b_1 b_2 … b_n with b_i b_{i+1} = 0 for 1 ≤ i < n, that is, a binary string without two consecutive ones. The Fibonacci cube Γ_n (n ≥ 1) is the subgraph of Q_n induced by the Fibonacci strings of length n.[1](https://www.sciencedirect.com/science/article/pii/S0012365X05002748) Equivalently, Γ_n is obtained from Q_n by removing every vertex that contains at least two consecutive 1s; the smallest cases are Γ_1 = K_2 and Γ_2, the path on three vertices.[2](https://users.fmf.uni-lj.si/klavzar/preprints/FibonacciCubesRevised.pdf)
Hsu's original definition ran through integer codes: the order-n Fibonacci code of an integer i is a sequence of n−2 binary digits with no two consecutive 1s, and Γ_n joins two codes when their [Hamming distance](https://www.edgepedia.org/hamming-distance) is 1.[6](https://www.fq.math.ca/Scanned/31-1/hsu.pdf) Two other equivalent definitions exist: Γ_n is the graph of the distributive lattice of order-ideals of a fence poset, and it is the simplex graph of the complement graph of a [path graph](https://www.edgepedia.org/path-graph), the latter characterization due to Alikhani and Ghanbari (2024).[5](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v18i1p55/pdf) • [9](https://mathworld.wolfram.com/FibonacciCubeGraph.html)
## Basic enumeration
The vertex count follows from counting Fibonacci strings. The number of such strings of length d satisfies the Fibonacci recurrence and equals a Fibonacci number; specifically, \( |V(\Gamma_n)| = F_{n+2} \) for n ≥ 0.[5](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v18i1p55/pdf) • [4](https://ar5iv.labs.arxiv.org/html/1306.5154) [Zeckendorf's theorem](https://www.edgepedia.org/zeckendorfs-theorem) gives the same count from the other direction: every non-negative integer i with 0 ≤ i < F_n has a unique representation as a sum of non-consecutive Fibonacci numbers, and these representations correspond to vertices of Γ_{n−2}, giving |V(Γ_{n−2})| = F_n.[10](https://www.fq.math.ca/Papers1/43-3/paper43-3-10.pdf) In Hsu's original construction the vertex set of Γ_n is the set of integers {0, 1, …, F_n − 1}, with edges between vertices whose Fibonacci codes differ in exactly one bit.[6](https://www.fq.math.ca/Scanned/31-1/hsu.pdf)
The closed form of the edge count is
\[ |E(\Gamma_n)| = \frac{nF_{n+1} + 2(n+1)F_n}{5}. \]
It also follows from the recursive structure: |E(Γ_n)| = |E(Γ_{n−1})| + |E(Γ_{n−2})| + |V(Γ_{n−2})|.[1](https://www.sciencedirect.com/science/article/pii/S0012365X05002748) Published statements of the closed form differ by a factor of 5: one survey preprint states |E(Γ_n)| = nF_{n+1} + 2(n+1)F_n, while the asymptotic study and OEIS A001629 give the version divided by 5, which is the correct one (it yields 2 edges for Γ_2, matching the 3-vertex path).[4](https://ar5iv.labs.arxiv.org/html/1306.5154) • [2](https://users.fmf.uni-lj.si/klavzar/preprints/FibonacciCubesRevised.pdf)
## Structural properties
**Median and partial cube.** Fibonacci cubes are median graphs, and every median graph is a partial cube, so Γ_n isometrically embeds into Q_n: distances between vertices in Γ_n equal their Hamming distances in the ambient hypercube.[5](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v18i1p55/pdf) Extended Fibonacci cubes and Lucas cubes are median for the same reason.[1](https://www.sciencedirect.com/science/article/pii/S0012365X05002748)
**Distances and connectivity.** Hsu proved that the diameter of Γ_n is n.[6](https://www.fq.math.ca/Scanned/31-1/hsu.pdf) Munarini and Zagaglia Salvi proved the radius is ⌈n/2⌉ and determined the center; Castro and Mollard later counted vertices by eccentricity.[2](https://users.fmf.uni-lj.si/klavzar/preprints/FibonacciCubesRevised.pdf) For a Fibonacci cube with N nodes, the diameter, [edge connectivity](https://www.edgepedia.org/edge-connectivity), and node connectivity are all logarithmic in N, which is what makes the family usable as an interconnection network despite its sparse, asymmetric links.[8](https://dl.acm.org/doi/10.1109/71.205649)
**Paths and degrees.** The fundamental decomposition shows Γ_n contains Hamiltonian paths, and the survey records its independence number as α(Γ_n) = max{e_n, o_n}.[2](https://users.fmf.uni-lj.si/klavzar/preprints/FibonacciCubesRevised.pdf) Fibonacci cube graphs are traceable and bipartite, and are Hamiltonian for n = 3, 7, 10, ….[9](https://mathworld.wolfram.com/FibonacciCubeGraph.html) The degree sequence has been studied in detail; its vertices are the Fibonacci strings of length n, with two vertices adjacent when they differ in precisely one bit.[11](https://www.sciencedirect.com/science/article/pii/S0012365X11001191) Asymptotically, the average degree divided by n tends to (5−√5)/5 ≈ 0.553, and the average eccentricity tends to (5+√5)/10 ≈ 0.724.[4](https://ar5iv.labs.arxiv.org/html/1306.5154)
## By the numbers
| Quantity | Value for Γ_n |
|---|---|
| Vertices | F_{n+2}[4](https://ar5iv.labs.arxiv.org/html/1306.5154) |
| Edges | (nF_{n+1} + 2(n+1)F_n)/5[4](https://ar5iv.labs.arxiv.org/html/1306.5154) |
| Diameter | n[6](https://www.fq.math.ca/Scanned/31-1/hsu.pdf) |
| Radius | ⌈n/2⌉[2](https://users.fmf.uni-lj.si/klavzar/preprints/FibonacciCubesRevised.pdf) |
| Wiener index | (4(n+1)F(n)² + (9n+2)F(n)F(n+1) + 6n F(n+1)²)/25, with F the Fibonacci numbers (Klavžar and Mollard, 2014)[12](https://oeis.org/A238419/internal) |
| Hosoya polynomial | Row n of OEIS A246173; its first coefficient T(n,1) is the edge count, and Σ k·T(n,k) equals the Wiener index[13](https://oeis.org/A246173) |
| Asymptotic average degree / n | (5−√5)/5[4](https://ar5iv.labs.arxiv.org/html/1306.5154) |
| Hypercube density | (1−1/√5)/log₂φ, where φ is the golden ratio[4](https://ar5iv.labs.arxiv.org/html/1306.5154) |
The eccentricity of a vertex equals the depth of the associated leaf in the Fibonacci tree.[4](https://ar5iv.labs.arxiv.org/html/1306.5154)
## How it compares with related graph families
**Hypercubes.** Hsu's motivation was to obtain networks with hypercube-like properties on vertex sets whose order is not a power of two; Γ_n has F_{n+2} vertices where Q_n has 2^n.[2](https://users.fmf.uni-lj.si/klavzar/preprints/FibonacciCubesRevised.pdf) The hypercube density (1−1/√5)/log₂φ quantifies the trade-off.[4](https://ar5iv.labs.arxiv.org/html/1306.5154)
**Lucas cubes.** The Lucas cube Λ_n is the subgraph of Q_n induced by Fibonacci strings in which not both b_1 and b_n equal 1; it has L_n = F_{n−1} + F_{n+1} vertices and nF_{n−1} edges for n ≥ 2.[1](https://www.sciencedirect.com/science/article/pii/S0012365X05002748) • [2](https://users.fmf.uni-lj.si/klavzar/preprints/FibonacciCubesRevised.pdf) Lucas cubes form a symmetrization of Fibonacci cubes and appear as resonance graphs of cyclic polyphenantrenes.[2](https://users.fmf.uni-lj.si/klavzar/preprints/FibonacciCubesRevised.pdf)
**Other variants.** Extended Fibonacci cubes factor as Γ_n^i = Γ_{n−i} □ Q_i, so their vertex, edge, and square counts reduce to those of Fibonacci cubes and hypercubes.[1](https://www.sciencedirect.com/science/article/pii/S0012365X05002748) Enhanced Fibonacci cubes, introduced by Qian and Wu, contain Fibonacci cubes as subgraphs while adding properties such as Hamiltonian cycles.[2](https://users.fmf.uni-lj.si/klavzar/preprints/FibonacciCubesRevised.pdf) The k-Fibonacci cube Γ_n^k has the same f_{n+2} vertices as Γ_n with a different edge set, and its edge count, average degree, degree sequence, and contained hypercubes have been computed.[7](https://cs.ucsb.edu/sites/default/files/documents/k-fibonacci_cubes_egecioglu_saygi_nov29_2019.pdf) More generally, the generalized Fibonacci cube Q_d(f) deletes from Q_d all vertices containing a given binary string f as a substring, with Γ_d = Q_d(11); the isometric-embedding question for Q_d(f) is completely solved for strings of length at most five and for strings of at most three blocks, and the only median-closed generalized Fibonacci cubes are paths and Fibonacci cubes.[3](https://users.fmf.uni-lj.si/klavzar/preprints/GFC-revised.pdf) For admissible f with |f| ≥ 2 and d ≥ |f|, the maximum degree and diameter of Q_d(f) both equal d.[3](https://users.fmf.uni-lj.si/klavzar/preprints/GFC-revised.pdf) Fibonacci cubes also belong to the daisy cubes, a family of isometrical subgraphs of hypercubes.[14](https://arxiv.org/html/2502.07520)
## Connections to Zeckendorf representations and Fibonacci numbers
The decomposition Γ_n = 0Γ_{n−1} + 10Γ_{n−2} mirrors the Fibonacci recurrence: vertices beginning with 0 form a copy of Γ_{n−1}, vertices beginning with 10 form a copy of Γ_{n−2}, and link edges join the two parts.[7](https://cs.ucsb.edu/sites/default/files/documents/k-fibonacci_cubes_egecioglu_saygi_nov29_2019.pdf) Fibonacci numbers then reappear throughout the invariants: the vertex and edge counts, the [Wiener index](https://www.edgepedia.org/wiener-index) formula, the Hosoya polynomial coefficients, and the asymptotic constants built on the golden ratio φ.[4](https://ar5iv.labs.arxiv.org/html/1306.5154) • [12](https://oeis.org/A238419/internal)
## Applications in chemical graph theory
A fibonacene (also called fibonaccene) is a zig-zag unbranched catacondensed benzenoid hydrocarbon, a hexagonal chain in which no three hexagons are linearly attached; its molecular-graph properties are often related to Fibonacci numbers.[15](https://match.pmf.kg.ac.rs/electronic_versions/Match55/n1/match55n1_39-54.pdf) • [2](https://users.fmf.uni-lj.si/klavzar/preprints/FibonacciCubesRevised.pdf) An h-fibonacene molecular graph has 4h + 2 vertices, of which 2h + 4 have degree 2 and 2h − 2 have degree 3, and 5h + 1 edges.[15](https://match.pmf.kg.ac.rs/electronic_versions/Match55/n1/match55n1_39-54.pdf) The central theorem of this connection is that the resonance graph of any fibonacene with n hexagons is isomorphic to Γ_n; Zhang, Ou, and Yao generalized the result to plane bipartite graphs.[2](https://users.fmf.uni-lj.si/klavzar/preprints/FibonacciCubesRevised.pdf) • [10](https://www.fq.math.ca/Papers1/43-3/paper43-3-10.pdf) Consistently, the number of Kekulé structures of the zig-zag fibonacene Z_h equals the (h+2)-nd Fibonacci number, matching |V(Γ_h)| = F_{h+2}.[15](https://match.pmf.kg.ac.rs/electronic_versions/Match55/n1/match55n1_39-54.pdf) Fibonacci cubes also led to the concept of the Fibonacci dimension of a graph.[11](https://www.sciencedirect.com/science/article/pii/S0012365X11001191)
## Recent developments
**Simplex-graph characterization.** Alikhani and Ghanbari (2024) showed that the Fibonacci cube is the simplex graph of the complement of a path graph.[9](https://mathworld.wolfram.com/FibonacciCubeGraph.html)
**Fibonacci p-cubes.** Jianxin Wei and Yujun Yang introduced Γ_n^p, subgraphs of hypercubes induced by strings with at least p consecutive 0s between two 1s; a 2025 paper proved their conjectured cube-polynomial expression, derived the distance cube polynomial, and computed the Mostar index, with Mo(Γ_n^p) = F_{n+p+1}^p Σ_{i=1}^{n} F_i^p F_{n−i+1}^p − 2Σ_{i=1}^{n} (F_i^p F_{n−i+1}^p)².[14](https://arxiv.org/html/2502.07520)
**Higher-order generalizations.** A 2025 preprint studies p-th order Fibonacci cubes Γ_n^(p), induced by strings with no p consecutive 1s, links their vertices to integer compositions with parts in {1, …, p}, and computes order, size, cube polynomial, and generating functions, with p-nomial coefficients playing the role of binomial coefficients; it also connects maximal induced hypercubes in Γ_n^p to vertices of (p+1)-th order generalized Fibonacci cubes.[16](https://ar5iv.labs.arxiv.org/html/2507.16387) Following Mollard, Q_n(1^k) is called the k-th order Fibonacci cube Γ_n^(k), and a 2026 paper studies its size.[17](https://arxiv.org/html/2601.17273) A paper in Ars Mathematica Contemporanea treats Fibonacci (p,r)-cubes.[18](https://combinatorialpress.com/ars-articles/volume-161/on-fibonacci-pr-cubes/)
**Fibonacci dimension.** Every partial cube embeds isometrically in some Fibonacci cube Γ_d, and the minimum such d is the Fibonacci dimension fdim(G), satisfying idim(G) ≤ fdim(G) ≤ 2·idim(G) − 1; deciding whether idim(G) = fdim(G) is NP-complete in general but always true for trees, per a 2025 CPM paper on generalized Fibonacci cubes Q_k(S).[19](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.10)
**Other directions.** Metallic and metallic-Lucas cubes, generalizations of the Fibonacci and Lucas cubes, received explicit Wiener and Mostar index formulas in a 2026 Applied Mathematics and [Computation](https://www.edgepedia.org/computation) paper.[20](https://dl.acm.org/doi/10.1016/j.amc.2026.130217) And the pebbling number has been computed: π(Γ_n) = 2^n for n ≤ 6, equal to that of the ambient hypercube Q_n despite Γ_n having far fewer vertices, with a conjecture that π(Γ_n) = 2^n for all n.[21](https://doi.org/10.48550/arxiv.2605.04328)
## References
1. [Sandi Klavžar (2005). On median nature and enumerative properties of Fibonacci-like cubes. Discrete Mathematics 299.](https://www.sciencedirect.com/science/article/pii/S0012365X05002748)
2. [Sandi Klavžar and Michel Mollard. Fibonacci Cubes: A Survey.](https://users.fmf.uni-lj.si/klavzar/preprints/FibonacciCubesRevised.pdf)
3. [Sandi Klavžar and A. Ashraf. Generalized Fibonacci Cubes.](https://users.fmf.uni-lj.si/klavzar/preprints/GFC-revised.pdf)
4. [A. Ilić, S. Klavžar, et al. Asymptotic properties of Fibonacci cubes and Lucas cubes.](https://ar5iv.labs.arxiv.org/html/1306.5154)
5. [The Fibonacci Dimension of a Graph. Electronic Journal of Combinatorics 18(1), #P55 (2011).](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v18i1p55/pdf)
6. [Wen-Ping Hsu (1993). Fibonacci Cubes—A Class of Self-Similar Graphs. Fibonacci Quarterly 31(1).](https://www.fq.math.ca/Scanned/31-1/hsu.pdf)
7. [Ö. Egecioğlu and A. Sayğı (2019). k-Fibonacci Cubes.](https://cs.ucsb.edu/sites/default/files/documents/k-fibonacci_cubes_egecioglu_saygi_nov29_2019.pdf)
8. [Wen-Ping Hsu (1993). Fibonacci Cubes—A New Interconnection Topology. IEEE Transactions on Parallel and Distributed Systems.](https://dl.acm.org/doi/10.1109/71.205649)
9. [Fibonacci Cube Graph. Wolfram MathWorld.](https://mathworld.wolfram.com/FibonacciCubeGraph.html)
10. [Fibonacci Cubes Are the Resonance Graphs of Fibonaccenes. Fibonacci Quarterly 43(3).](https://www.fq.math.ca/Papers1/43-3/paper43-3-10.pdf)
11. [The degree sequence of Fibonacci and Lucas cubes. Discrete Mathematics.](https://www.sciencedirect.com/science/article/pii/S0012365X11001191)
12. [A238419: Wiener index of the Fibonacci cube. OEIS.](https://oeis.org/A238419/internal)
13. [A246173: Hosoya polynomial coefficients of the Fibonacci cube. OEIS.](https://oeis.org/A246173)
14. [Some new results about Fibonacci p-cubes. arXiv (2025).](https://arxiv.org/html/2502.07520)
15. [Chemical Graph Theory of Fibonacenes. MATCH Communications in Mathematical and in Computer Chemistry 55 (2006).](https://match.pmf.kg.ac.rs/electronic_versions/Match55/n1/match55n1_39-54.pdf)
16. [p-th order generalized Fibonacci cubes and maximal cubes in Fibonacci p-cubes. arXiv (2025).](https://ar5iv.labs.arxiv.org/html/2507.16387)
17. [The size of k-th order generalized Fibonacci cubes. arXiv (2026).](https://arxiv.org/html/2601.17273)
18. [On Fibonacci (p,r)-cubes. Ars Mathematica Contemporanea.](https://combinatorialpress.com/ars-articles/volume-161/on-fibonacci-pr-cubes/)
19. [A Family of Partial Cubes with Minimal Fibonacci Dimension. LIPIcs CPM 2025.](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.10)
20. [On distance-based invariants of two classes of partial cubes. Applied Mathematics and Computation (2026).](https://dl.acm.org/doi/10.1016/j.amc.2026.130217)
21. [The pebbling number of Fibonacci cubes.](https://doi.org/10.48550/arxiv.2605.04328)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Graph theory › Graph theory subfields and named results › Chemical graph theory*
*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license