No label defined (Q4033752)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 166137
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 166137 |
Statements
16 May 1993
0 references
self-similar graphs
0 references
Fibonacci cube
0 references
distributed networks
0 references
0.8551101684570312
0 references
0.8544046878814697
0 references
0.8397105932235718
0 references
0.8349854946136475
0 references
0.8339539766311646
0 references
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.
0 references