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.
Read more about this topic: Fibonacci Cube
Famous quotes containing the word properties:
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)