scientific article; zbMATH DE number 166137

From MaRDI portal
Publication:4033752





The Fibonacci cube is a new class of graphs that are inspired by the famous numbers. Because of the rich properties of the Fibonacci numbers, the graph also shows interesting properties. For a graph with \(N\) nodes, it is known that the diameter, the edge connectivity, and the node connectivity of the Fibonacci cube are in the order of \(O(\log N)\), which are similar to the Boolean cube (or hypercube, \(n\)-cube, cosmic cube). A possible application of the Fibonacci cube is in the interconnection of large- scale multi-computers or distributed networks. Here we show that the Fibonacci cube has attractive recurrent structures (called self- similarity) in the following sense: 1. A Fibonacci cube can be decomposed into subgraphs which are also Fibonacci cubes by themselves; 2. By suitably defining equivalence classes of vertices in the Fibonacci cube and merging the edges between vertices in different classes in a natural fashion, the resulting graph (of the equivalence classes) is again a Fibonacci cube. This structural recurrence is useful to derive (divide-and-conquer) algorithms for a parallel computer based on the Fibonacci cube. It is also useful to derive the embeddings of other types of graphs. This paper is organized as follows. Section 2 defines the Fibonacci cube based on the Fibonacci representation of integers. Section 3 provides a characterization of the new graph and discusses various decompositions. Section 4 briefly summarizes the results that are presented and discusses possible applications.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4033752)