HIERARCHIC GRAPHS BASED ON THE FIBONACCI NUMBERS

Abstract

In this paper, a new class of hierarchically definable graphs are proposed and they are proper subgraphs of Hierarchic Cubic graphs. These graphs are based on the Fibonacci series by changing initial conditions. When the initial conditions are changed, then the structure of obtained graph will be changed. Thus, we obtained a series of hierarchically definable graphs. The obtained graphs have logarithmic node degrees and diameters in terms of number of nodes. Thus they are comparable with incomplete hypercube graph. Sometimes, incomplete hypercube may include at least one node whose node degree is 1. This is an unwilling case, however, the obtained graphs do not have nodes of degree 1 except initial conditions graphs. Hypercube graph and hierarchic cubic network are recursively definable graphs and the obtained graphs are proper subgraphs of hierarchic cubic network. Thus, it is important to verify that the constructed graphs are also recursively definable graphs. We prove that the obtained graphs are selfsimilar graphs or decomposable in terms of lower sized graphs in the same category.