On recursively directed hypercubes (Q1599526)

Summary: 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\).