scientific article; zbMATH DE number 166137
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.
- Generalized linear recursive networks: topological and routing properties
- Fibonacci \((p,r)\)-cubes which are median graphs
- Structure of Fibonacci cubes: a survey
- The radius and center of Fibonacci-run graphs
- The devil is in the details: spectrum and eigenvalue distribution of the discrete Preisach memory model
- Determining which Fibonacci (\(p,r\))-cubes can be \(Z\)-transformation graphs
- \(\Theta\)-graceful labelings of partial cubes
- On median nature and enumerative properties of Fibonacci-like cubes
- Generalized Lucas graphs
- The use of Fibonacci numbers for design of some parallel algorithms
- Mincuts in generalized Fibonacci graphs of degree 3
- Two applicable network families: Fibonacci cubes and Sierpiński graphs
- Fibonacci hypercube
- scientific article; zbMATH DE number 647814 (Why is no real title available?)
- scientific article; zbMATH DE number 2060177 (Why is no real title available?)
- scientific article; zbMATH DE number 841630 (Why is no real title available?)
- On d-Fibonacci digraphs
- Some diameter notions of Fibonacci cubes
- Topological properties of Fibonacci networks
- On Fibonacci-like cubes
- Zeckendorf theorem and Fibonacci cubes
- On embedding Fibonacci meshes on Fiboacci cube networks
- The Fibonacci hypercube
- Fibonacci Cubes with Applications and Variations
- Metallic cubes
- Sharp mosaic dimension of matching toggle graphs, with an application to fibonaccenes
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)