On Recursively Directed Hypercubes

Abstract

In this paper we introduce the recursively directed hypercubes, and analyze some of their structural properties. We show that every recursively directed hypercube is acyclic, and has a unique pair of source and sink nodes. The main contribution of the paper is an analysis of distances between the nodes in such a graph. We show that the distance from the source node to any other node, and from any node to the sink node is bounded by $n+1$, where $n$ is the dimension of the hypercube, but the diameter of a recursively directed hypercube may be exponential in $n$.