Line digraph iterations and the (d,k) problem for directed graphs

Abstract

We consider in this paper the (d,k) problem for directed graphs: to maximize the number of vertices in a digraph of degree d and diameter k. For any values of d and k, we construct a graph with a number of vertices larger than (d 2 -1)/d 2 times the (non-attainable) Moore bound. In particular, this solves the (d,k) digraph problem for k=2. We also show that these graphs can be obtained as line digraph iterations and that this technique provides us with a simple local routing algorithm for the corresponding networks.