On Diregularity of Digraphs of Defect at Most Two

Dafik 1, Mirka Miller2,3, Costas Iliopoulos4, Zdenek Ryjacek3
1Department of Mathematics Education University of Jember, Indonesia
2School of Electrical Engineering and Computer Sciences The University of Newcastle, Australia
3Department of Mathematics University of West Bohemia, Plzei, Czech Republic
4Department of Computer Science Kings College, London, UK

Abstract

Since Moore digraphs do not exist for \( k \neq 1 \) and \( d \neq 1 \), the problem of finding digraphs of out-degree \( d \geq 2 \), diameter \( k \geq 2 \) and order close to the Moore bound becomes an interesting problem. To prove the non-existence of such digraphs or to assist in their construction (if they exist), we first may wish to establish some properties that such digraphs must possess. In this paper, we consider the diregularity of such digraphs. It is easy to show that any digraph with out-degree at most \( d \geq 2 \), diameter \( k \geq 2 \) and order one or two less than the 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 either diregular or almost diregular. Additionally, in the case of defect one, we present a new, simpler, and shorter proof that a digraph of defect one must be diregular, and in the case of defect two and for \( d = 2 \) and \( k \geq 3 \), we present an alternative proof that a digraph of defect two must be diregular.