Jump to content

Fibonacci cube

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Pontus (talk | contribs) at 12:56, 12 January 2018 (→Properties and algorithms). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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. 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.

Fibonacci cubes (drawn in red) as subgraphs of hypercubes

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.[1]

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.[2] 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.[3] 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 > ...[4] 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,[5] 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).[6]

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.[7]

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.[8] The diameter of a Fibonacci cube of order n is n, and its radius is n/2 (again, rounded up to the nearest integer).[9]

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.[7] Fibonacci cubes also support efficient protocols for routing and broadcasting in distributed computations.[10]

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.[2]

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.

Notes

  1. ^ Klavžar (2011), pp. 3–4.
  2. ^ a b Klavžar (2011), p.3.
  3. ^ Klavžar (2005); Klavžar (2011), Theorem 5.1, p.10.
  4. ^ Gansner (1982) calls the fact that this lattice has a Fibonacci number of elements a “well known fact,” while Stanley (1986) asks for a description of it in an exercise. See also Höft & Höft (1985), Beck (1990), and Salvi & Salvi (2008).
  5. ^ Propp (1997).
  6. ^ Klavžar (2011), pp. 4–5.
  7. ^ a b Cong, Zheng & Sharma (1993).
  8. ^ Klavžar (2011), p.6.
  9. ^ Klavžar (2011), p.9.
  10. ^ Hsu (1993); Stojmenovic 1998.

References

  • Beck, István (1990), "Partial orders and the Fibonacci numbers", Fibonacci Quarterly, 28 (2): 172–174, MR 1051291.
  • 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, MR 0675856.
  • Höft, Hartmut; Höft, Margret (1985), "A Fibonacci sequence of distributive lattices", Fibonacci Quarterly, 23 (3): 232–237, MR 0806293.
  • 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, vol. 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" (PDF), IMFM Preprint Series, 49 (1150), Ljubljana, Slovenia: Institute of Mathematics, Physics and Mechanics.
  • 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 {{citation}}: Unknown parameter |deadurl= ignored (|url-status= suggested) (help).
  • 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, arXiv:math.CO/9801066.
  • Salvi, Rodolfo; Salvi, Norma Zagaglia (2008), "Alternating unimodal sequences of Whitney numbers", Ars Combinatoria, 87: 105–117, MR 2414008.
  • Stanley, Richard P. (1986), Enumerative Combinatorics, Wadsworth, Inc. Exercise 3.23a, page 157.
  • Stojmenovic, Ivan (1998), "Optimal deadlock-free routing and broadcasting on Fibonacci cube networks" (PDF), Utilitas Mathematica, 53: 159–166, archived from the original (PDF) on 2011-07-25 {{citation}}: Unknown parameter |deadurl= ignored (|url-status= suggested) (help).
  • 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, MR 2510538.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Fibonacci_cube&oldid=819991799"