Fibonacci cube

Short description: Family of graphs based on the Fibonacci sequence

In the mathematical field of graph theory, the Fibonacci cubes or Fibonacci networks are a family of undirected graphs with rich recursive properties derived from its origin in number theory. Mathematically they are similar to the hypercube graphs, but with a Fibonacci number of vertices. Fibonacci cubes were first explicitly defined in (Hsu 1993) in the context of interconnection topologies for connecting parallel or distributed systems. They have also been applied in chemical graph theory.

The Fibonacci cube may be defined in terms of Fibonacci codes and Hamming distance, independent sets of vertices in path graphs, or via distributive lattices.

Definition

Like the hypercube graph, the vertices of the Fibonacci cube of order n may be labeled with bitstrings of length n, in such a way that two vertices are adjacent whenever their labels differ in a single bit. However, in a Fibonacci cube, the only labels that are allowed are bitstrings with no two consecutive 1 bits. If the labels of the hypercube are interpreted as binary numbers, the labels in the Fibonacci cube are a subset, the fibbinary numbers. There are F_n + 2 labels possible, where F_n denotes the nth Fibonacci number, and therefore there are F_n + 2 vertices in the Fibonacci cube of order n.

Fibonacci cubes (drawn in red) as subgraphs of hypercubes

The nodes of such a network may be assigned consecutive integers from 0 to F_n + 2 − 1; the bitstrings corresponding to these numbers are given by their Zeckendorf representations.

The Fibonacci cube of order 6

Algebraic structure

The Fibonacci cube of order n is the simplex graph of the complement graph of an n-vertex path graph. That is, each vertex in the Fibonacci cube represents a clique in the path complement graph, or equivalently an independent set in the path itself; two Fibonacci cube vertices are adjacent if the cliques or independent sets that they represent differ by the addition or removal of a single element. Therefore, like other simplex graphs, Fibonacci cubes are median graphs and more generally partial cubes. The median of any three vertices in a Fibonacci cube may be found by computing the bitwise majority function of the three labels; if each of the three labels has no two consecutive 1 bits, the same is true of their majority.

The Fibonacci cube is also the graph of a distributive lattice that may be obtained via Birkhoff's representation theorem from a zigzag poset, a partially ordered set defined by an alternating sequence of order relations a < b > c < d > e < f > ... There is also an alternative graph-theoretic description of the same lattice: the independent sets of any bipartite graph may be given a partial order in which one independent set is less than another if they differ by removing elements from one side of the bipartition and adding elements to the other side of the bipartition; with this order, the independent sets form a distributive lattice, and applying this construction to a path graph results in the lattice associated with the Fibonacci cube.

Properties and algorithms

The Fibonacci cube of order n may be partitioned into a Fibonacci cube of order n − 1 (the nodes with labels beginning with a 0 bit) and a Fibonacci cube of order n − 2 (the nodes with labels beginning with a 1 bit).

Every Fibonacci cube has a Hamiltonian path. More specifically, there exists a path that obeys the partition described above: it visits the nodes with first bit 0 and the nodes with first bit 1 in two contiguous subsequences. Within these two subsequences, the path can be constructed recursively by the same rule, linking the two subsequences at the ends of the subsequences at which the second bit is 0. Thus, e.g., in the Fibonacci cube of order 4, the sequence constructed in this way is (0100-0101-0001-0000-0010)-(1010-1000-1001), where the parentheses demark the subsequences within the two subgraphs of the partition. Fibonacci cubes with an even number of nodes greater than two have a Hamiltonian cycle.

(Munarini Salvi) investigate the radius and independence number of Fibonacci cubes. Because these graphs are bipartite and have Hamiltonian paths, their maximum independent sets have a number of vertices that is equal to half of the number of vertices in the whole graph, rounded up to the nearest integer. The diameter of a Fibonacci cube of order n is n, and its radius is n/2 (again, rounded up to the nearest integer).

(Taranenko Vesel) showed that it is possible to test whether a graph is a Fibonacci cube in time near-linear in its size.

Applications

(Hsu 1993) and (Hsu Page) suggested using Fibonacci cubes as a network topology in parallel computing. As a communications network, the Fibonacci cube has beneficial properties similar to those of the hypercube: the number of incident edges per vertex is at most n/2 and the diameter of the network is at most n, both proportional to the logarithm of the number of vertices, and the ability of the network to be partitioned into smaller networks of the same type allows it to be split among multiple parallel computation tasks. Fibonacci cubes also support efficient protocols for routing and broadcasting in distributed computations.

(Klavžar Žigert) apply Fibonacci cubes in chemical graph theory as a description of the family of perfect matchings of certain molecular graphs. For a molecular structure described by a planar graph G, the resonance graph or (Z-transformation graph) of G is a graph whose vertices describe perfect matchings of G and whose edges connect pairs of perfect matchings whose symmetric difference is an interior face of G. Polycyclic aromatic hydrocarbons may be described as subgraphs of a hexagonal tiling of the plane, and the resonance graph describes possible double-bond structures of these molecules. As (Klavžar Žigert) show, hydrocarbons formed by chains of hexagons, linked edge-to-edge with no three adjacent hexagons in a line, have resonance graphs that are exactly the Fibonacci graphs. More generally (Zhang Ou) described the class of planar bipartite graphs that have Fibonacci cubes as their resonance graphs.

Related graphs

Generalized Fibonacci cubes were presented by (Hsu Chung) based on the k-th order Fibonacci numbers, which were later further extended to a larger class of networks called the Linear Recursive Networks by (Hsu Chung) based on more general forms of linear recursions. (Wu 1997) modified the second order Fibonacci cubes based on different initial conditions. Another related graph is the Lucas cube, a graph with a Lucas number of vertices defined from the Fibonacci cube by forbidding a 1 bit in both the first and last positions of each bitstring; (Dedó Torri) investigated the coloring properties of both Fibonacci cubes and Lucas cubes.

References

• Beck, István (1990), "Partial orders and the Fibonacci numbers", Fibonacci Quarterly 28 (2): 172–174 .
• Cong, B.; Zheng, S. Q.; Sharma, S. (1993), "On simulations of linear arrays, rings and 2D meshes on Fibonacci cube networks", Proc. 7th Int. Parallel Processing Symposium, pp. 748–751, doi:10.1109/IPPS.1993.262788 .
• Dedó, Ernesto; Torri, Damiano; Salvi, Norma Zagaglia (2002), "The observability of the Fibonacci and the Lucas cubes", Discrete Mathematics 255 (1–3): 55–63, doi:10.1016/S0012-365X(01)00387-9 .
• Gansner, Emden R. (1982), "On the lattice of order ideals of an up-down poset", Discrete Mathematics 39 (2): 113–122, doi:10.1016/0012-365X(82)90134-0 .
• Höft, Hartmut; Höft, Margret (1985), "A Fibonacci sequence of distributive lattices", Fibonacci Quarterly 23 (3): 232–237 .
• Hsu, W.-J. (1993), "Fibonacci cubes: a new interconnection topology", IEEE Transactions on Parallel and Distributed Systems 4 (1): 3–12, doi:10.1109/71.205649 .
• Hsu, W.-J.; Chung, M. J. (1993), "Generalized Fibonacci cubes", 1993 International Conference on Parallel Processing - ICPP'93, 1, pp. 299–302, doi:10.1109/ICPP.1993.95 .
• Hsu, W.-J.; Page, C. V.; Liu, J.-S. (1993), "Fibonacci cubes: a class of self-similar graphs", Fibonacci Quarterly 31 (1): 65–72 .
• Hsu, W.-J.; Chung, M. J.; Das, A. (1997), "Linear recursive networks and their applications in distributed systems", IEEE Transactions on Parallel and Distributed Systems 8 (7): 673–680, doi:10.1109/71.598343 .
• Klavžar, Sandi (2005), "On median nature and enumerative properties of Fibonacci-like cubes", Discrete Mathematics 299 (1–3): 145–153, doi:10.1016/j.disc.2004.02.023 .
• Klavžar, Sandi (2011), "Structure of Fibonacci cubes: a survey", IMFM Preprint Series (Ljubljana, Slovenia: Institute of Mathematics, Physics and Mechanics) 49 (1150), http://www.imfm.si/preprinti/PDF/01150.pdf .
• Klavžar, Sandi; Žigert, Petra (2005), "Fibonacci cubes are the resonance graphs of Fibonaccenes", Fibonacci Quarterly 43 (3): 269–276, archived from the original on 2007-02-08, https://web.archive.org/web/20070208125133/http://www-mat.pfmb.uni-mb.si/personal/klavzar/preprints/Fibonacci6.ps .
• Munarini, Emanuele; Salvi, Norma Zagaglia (2002), "Structural and enumerative properties of the Fibonacci cubes", Discrete Mathematics 255 (1–3): 317–324, doi:10.1016/S0012-365X(01)00407-1 .
• Propp, James (1997), "Generating random elements of finite distributive lattices", Electronic Journal of Combinatorics 4 (2): R15, doi:10.37236/1330 .
• Salvi, Rodolfo; Salvi, Norma Zagaglia (2008), "Alternating unimodal sequences of Whitney numbers", Ars Combinatoria 87: 105–117 .
• Enumerative Combinatorics, Wadsworth, Inc., 1986  Exercise 3.23a, page 157.
• Stojmenovic, Ivan (1998), "Optimal deadlock-free routing and broadcasting on Fibonacci cube networks", Utilitas Mathematica 53: 159–166, archived from the original on 2011-07-25, https://web.archive.org/web/20110725090758/http://www.site.uottawa.ca/~ivan/F51-fibonacciCube.PDF .
• Taranenko, A.; Vesel, A. (2007), "Fast recognition of Fibonacci cubes", Algorithmica 49 (2): 81–93, doi:10.1007/s00453-007-9026-5 .
• Wu, Jie (1997), "Extended Fibonacci cubes", IEEE Transactions on Parallel and Distributed Systems 8 (12): 1203–1210, doi:10.1109/71.640012 .
• Zhang, Heping; Ou, Lifeng; Yao, Haiyuan (2009), "Fibonacci-like cubes as Z-transformation graphs", Discrete Mathematics 309 (6): 1284–1293, doi:10.1016/j.disc.2008.01.053 .