On diregularity of digraphs of defect two

Abstract

Since Moore digraphs do not exist for k /= 1 and d /= 1, the problem of finding the existence of digraph of out-degree d >= 2 and diameter k >= 2 and order close to the Moore bound becomes an interesting problem. To prove the non-existence of such digraphs, we first may wish to establish their diregularity. It is easy to show that any digraph with out-degree at most d >= 2, diameter k >= 2 and order n = d + d^2 + ... + d^k-1, that is, two less than Moore bound must have all vertices of out-degree d. However, establishing the regularity or otherwise of the in-degree of such a digraph is not easy. In this paper we prove that all digraphs of defect two are out-regular and almost in-regular.