Digraphs with degree two and excess two are diregular

Tuite, James (2019). Digraphs with degree two and excess two are diregular. Discrete Mathematics, 342(5) pp. 1233–1244.

DOI: https://doi.org/10.1016/j.disc.2019.01.010

Abstract

A k-geodetic digraph with minimum out-degree d has excess ϵ if it has order M(d,k)+ϵ, where M(d,k) represents the Moore bound for out-degree d and diameter k. For given ϵ, it is simple to show that any such digraph must be out-regular with degree d for sufficiently large d and k. However, proving in-regularity is in general non-trivial. It has recently been shown that any digraph with excess ϵ=1 must be diregular. In this paper we prove that digraphs with minimum out-degree d=2 and excess ϵ=2 are diregular for k≥2.