Line Digraph Iterations and the (d, k) Digraph Problem

This paper studies the behavior of the diameter and the average distance between vertices of the line digraph of a given digraph. The results obtained are then applied to the so-called (d, k) digraph problem, that is, to maximize the number of vertices in a digraph of maximum out-degree d and diameter k. By line digraph iterations it is possible to construct digraphs with a number of vertices larger than (d2- l)/d2times the (nonattainable) Moore bound. In particular, this solves the (d, k) digraph problem for k = 2. Also, the line digraph technique provides us with a simple local routing algorithm for the corresponding networks.