 | ||
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.
Contents
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. There are Fn + 2 labels possible, where Fn denotes the nth Fibonacci number, and therefore there are Fn + 2 vertices in the Fibonacci cube of order n.
The nodes of such a network may be assigned consecutive integers from 0 to Fn + 2 − 1; the bitstrings corresponding to these numbers are given by their Zeckendorf representations.
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 (2002) 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 n2 (again, rounded up to the nearest integer).
Taranenko & Vesel (2007) 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 & 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.
Related graphs
Generalized Fibonacci cubes were presented by Hsu & Chung (1993) 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 & Das (1997) 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 & Salvi (2002) investigated the coloring properties of both Fibonacci cubes and Lucas cubes.