Nonexistence of almost Moore digraphs of degrees 4 and 5 with self-repeats

Abstract

An almost Moore (d,k)-digraph is a regular digraph of degree d>1, diameter k>1 and order N(d,k)=d+d2+⋯+dk. So far, their existence has only been shown for k=2, whilst it is known that there are no such digraphs for k=3, 4 and for d=2, 3 when k≥3. Furthermore, under certain assumptions, the nonexistence for the remaining cases has also been shown. In this paper, we prove that (4,k) and (5,k)-almost Moore digraphs with self-repeats do not exist for k≥5.

Nacho López: Supported in part by grants PID2020-115442RB-I00 and 2021 SGR-00434. Arnau Messegué: Supported in part by grants Margarita Sala and 2021SGR-00434. Josep M. Miret: Supported in part by grants PID2021-124613OB-I00 and 2021 SGR-00434.

Peer Reviewed

Postprint (published version)