On the structure of digraphs with order close to the Moore bound

The Moore bound for a diregular digraph of degree d and diameter k is M d;k = 1 + d + : : : + d k . It is known that digraphs of order M d;k do not exist for d ? 1 and k ? 1 ([24] or [6]). In this paper we study digraphs of degree d, diameter k and order M d;k \Gamma 1, denoted by (d; k)-digraphs. Miller and Fris showed that (2; k)- digraphs do not exist for k 3 [22]. Subsequently, we gave a necessary condition of the existence of (3; k)-digraphs, namely, (3; k)-digraphs do not exist if k is odd or if k + 1 does not divide 9 2 (3 k \Gamma 1) [3]. The (d; 2)-digraphs were considered in [4]. In this paper, we present further necessary conditions for the existence of (d; k)-digraphs. In particular, for d; k 3, we show that a (d; k)-digraph contains either no cycle of length k or exactly one cycle of length k. 1 Introduction By a digraph we mean a structure G = (V; A) where V (G) is a nonempty set of elements called vertices; and A(G) is a set of ordered pairs (u; v) of disti..