Fibonacci Cube - Applications

Applications

Hsu (1993) and Hsu, Page & Liu (1993) 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 (2005) 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 (2005) 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 & Yao (2009) described the class of planar bipartite graphs that have Fibonacci cubes as their resonance graphs.