Edge-Disjoint Fibonacci Trees in Hypercube

Abstract EN

The Fibonacci tree is a rooted binary tree whose number of vertices admit a recursive definition similar to the Fibonacci numbers.

In this paper, we prove that a hypercube of dimension h admits two edge-disjoint Fibonacci trees of height h, two edge-disjoint Fibonacci trees of height h-2, two edge-disjoint Fibonacci trees of height h-4 and so on, as subgraphs.

The result shows that an algorithm with Fibonacci trees as underlying data structure can be implemented concurrently on a hypercube network with no communication latency.