Abstract:
It is well known that the Moore digraph, namely a diregular digraph of degree d,
diameter k and order 1 + d + d 2 + ... + d k , only exists if d = 1 or k = 1. Let
(d,k)-digraph be a diregular digraph of degree d ≥ 2, diameter k ≥ 2 and order
d+d 2 +...+d k , one less than the Moore bound. Such a (d,k)-digraph is also called
an almost Moore digraph.
The study of the existence of an almost Moore digraph of degree d and diameter k
has received much attention. Fiol, Allegre and Yebra (1983) showed the existence
of (d,2)-digraphs for all d ≥ 2. In particular, for d = 2 and k = 2, Miller and
Fris (1988) enumerated all non-isomophic (2,2)-digraphs. Furthermore, Gimbert
(2001) showed that there is only one (d,2)-digraph for d ≥ 3. However for de-
gree 2 and diameter k ≥ 3, it is known that there is no (2,k)-digraph (Miller and
Fris, 1992). Furthermore, it was proved that there is no (3,k)-digraph with k ≥ 3
(Baskoro, Miller, Siran and Sutton, 2005). Recently, Conde, Gimbert, Gonzáles,
Miret, and Moreno (2008 & 2013) showed that no (d,k)-digraphs exist for k = 3,4
and for any d ≥ 2. Thus, the remaining case still open is the existence of (d,k)-
digraphs with d ≥ 4 and k ≥ 5.
Several necessary conditions for the existence of (d,k)-digraphs, for d ≥ 4 and
k ≥ 5, have been obtained. In this talk, we shall discuss some necessary conditions
for these (d,k)-digraphs. Open problems related to this study are also presented.