Open Problems in the Construction of Large Directed Graphs

Abstract

In this paper we consider the problem of how to construct directed graphs with given maximum out-degree and diameter. To deal with this problem, we describe several construction techniques. These fall into three broad categories, namely, algebraic specification, expansion and reduction methods.