Digraphs of degree two which miss the Moore bound by two

Miller, M. and Siran, J. (2001). Digraphs of degree two which miss the Moore bound by two. Discrete Mathematics, 226(1-3) pp. 269–280.

DOI: https://doi.org/10.1016/S0012-365X(00)00134-5


It is well known that Moore digraphs do not exist except for trivial cases (degree one or diameter one). Consequently, for a given maximum out-degree d and a given diameter, we wish to find a digraph whose order misses the Moore bound by the smallest possible ‘defect’. For diameter two and arbitrary degree there are digraphs which miss the Moore bound by one. No examples of such digraphs of diameter at least three are known, although several necessary conditions for their existence have been obtained. In the case of degree two, it has been shown that there are no digraphs of diameter greater than two and defect one. There are five nonisomorphic digraphs of degree two, diameter two and defect two. In this paper we prove that digraphs of degree two and diameter k3 which miss the Moore bound by two do not exist.

Viewing alternatives


Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions
No digital document available to download for this item

Item Actions