Fibonacci cube
Encyclopedia
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, studied in graph-theoretic mathematics
. Fibonacci cubes were first explicitly defined in 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 set
s of vertices in path graph
s, or via distributive lattice
s.
The nodes of such a network may be assigned consecutive integers from 0 to Fn + 2; the bitstrings corresponding to these numbers are given by their Zeckendorf representations.
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 graph
s and more generally partial cube
s. 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.
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.
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).
showed that it is possible to test whether a graph is a Fibonacci cube in time near-linear in its size.
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.
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 hydrocarbon
s 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 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 described the class of planar bipartite graphs that have Fibonacci cubes as their resonance graphs.
of vertices defined from the Fibonacci cube by forbidding a 1 bit in both the first and last positions of each bitstring; investigated the coloring properties of both Fibonacci cubes and Lucas cubes.
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
. Mathematically they are similar to the hypercube graphs, but with a Fibonacci number
Fibonacci number
In mathematics, the Fibonacci numbers are the numbers in the following integer sequence:0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\; ....
of vertices, studied in graph-theoretic mathematics
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
. Fibonacci cubes were first explicitly defined in in the context of interconnection topologies for connecting parallel or distributed systems. They have also been applied in chemical graph theory
Chemical graph theory
Chemical graph theory is the topology branch of mathematical chemistry which applies graph theory to mathematical modelling of chemical phenomena....
.
The Fibonacci cube may be defined in terms of Fibonacci codes and Hamming distance, independent set
Independent set (graph theory)
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
s of vertices in path graph
Path graph
In the mathematical field of graph theory, a path graph or linear graph is a particularly simple example of a tree, namely a tree with two or more vertices that is not branched at all, that is, contains only vertices of degree 2 and 1...
s, or via distributive lattice
Distributive lattice
In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...
s.
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 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; the bitstrings corresponding to these numbers are given by their Zeckendorf representations.
Algebraic structure
The Fibonacci cube of order n is the simplex graphSimplex graph
In graph theory, a branch of mathematics, the simplex graph κ of an undirected graph G is itself a graph, with one node for each clique in G...
of the complement graph
Complement graph
In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...
of an n-vertex path graph. That is, each vertex in the Fibonacci cube represents a clique
Clique (graph theory)
In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
in the path complement graph, or equivalently an independent set
Independent set
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
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 graph
Median graph
In mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m that belongs to shortest paths between any two of a, b, and c.The concept of median graphs has long been studied, for instance by or ...
s and more generally partial cube
Partial cube
In graph theory, a partial cube is a graph that is an isometric subgraph of a hypercube. In other words, a partial cube is a subgraph of a hypercube that preserves distances—the distance between any two vertices in the subgraph is the same as the distance between those vertices in the hypercube...
s. The median of any three vertices in a Fibonacci cube may be found by computing the bitwise majority function
Majority function
In Boolean logic, the majority function is a function from n inputs to one output. The value of the operation is false when n/2 or more arguments are false, and true otherwise....
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
Distributive lattice
In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...
that may be obtained via Birkhoff's representation theorem
Birkhoff's representation theorem
In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice can be represented as finite sets, in such a way that the lattice operations correspond to unions and intersections of sets...
from a zigzag poset, a partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
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
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
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
Hamiltonian path
In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle in an undirected graph that visits each vertex exactly once and also returns to the starting vertex...
. 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.
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).
showed that it is possible to test whether a graph is a Fibonacci cube in time near-linear in its size.
Applications
and suggested using Fibonacci cubes as a network topologyNetwork topology
Network topology is the layout pattern of interconnections of the various elements of a computer or biological network....
in parallel computing
Parallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
. 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
Routing
Routing is the process of selecting paths in a network along which to send network traffic. Routing is performed for many kinds of networks, including the telephone network , electronic data networks , and transportation networks...
and broadcasting in distributed computations.
apply Fibonacci cubes in chemical graph theory
Chemical graph theory
Chemical graph theory is the topology branch of mathematical chemistry which applies graph theory to mathematical modelling of chemical phenomena....
as a description of the family of perfect matchings of certain molecular graphs. For a molecular structure described by a planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
G, the resonance graph
Resonance (chemistry)
In chemistry, resonance or mesomerism is a way of describing delocalized electrons within certain molecules or polyatomic ions where the bonding cannot be expressed by one single Lewis formula...
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
Symmetric difference
In mathematics, the symmetric difference of two sets is the set of elements which are in either of the sets and not in their intersection. The symmetric difference of the sets A and B is commonly denoted by A\,\Delta\,B\,orA \ominus B....
is an interior face of G.
Polycyclic aromatic hydrocarbon
Polycyclic aromatic hydrocarbon
Polycyclic aromatic hydrocarbons , also known as poly-aromatic hydrocarbons or polynuclear aromatic hydrocarbons, are potent atmospheric pollutants that consist of fused aromatic rings and do not contain heteroatoms or carry substituents. Naphthalene is the simplest example of a PAH...
s 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 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 described the class of planar bipartite graphs that have Fibonacci cubes as their resonance graphs.
Related graphs
Generalized Fibonacci cubes were presented by 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 based on more general forms of linear recursions. modified the second order Fibonacci cubes based on different initial conditions. Another related graph is the Lucas cube, a graph with a Lucas numberLucas number
The Lucas numbers are an integer sequence named after the mathematician François Édouard Anatole Lucas , who studied both that sequence and the closely related Fibonacci numbers...
of vertices defined from the Fibonacci cube by forbidding a 1 bit in both the first and last positions of each bitstring; investigated the coloring properties of both Fibonacci cubes and Lucas cubes.