Fibonacci Cubes—a Class of Self-similar Graphs

Abstract

The Fibonacci cube [6] is a new class of graphs that are inspired by the famous numbers. Because of the rich properties of the Fibonacci numbers [1], the graph also shows interesting properties. For a graph with AT nodes, it is known [6] that the diameter, the edge connectivity, and the node connectivity of the Fibonacci cube are in the order of 0(log N), which are similar to the Boolean cube (or hypercube, «-cube, cosmic cube [9]). 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, §2) in the following sense:

Topics

    1 Figures and Tables

    Download Full PDF Version (Non-Commercial Use)