Digraphs with degree two and excess two are diregular

摘要

A k-geodetic digraph with minimum out-degree d has excess epsilon if it has order M(d, k) + epsilon, where M(d, k) represents the Moore bound for out-degree d and diameter k. For given epsilon, 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 epsilon = 1 must be diregular. In this paper we prove that digraphs with minimum out-degree d = 2 and excess epsilon = 2 are diregular for k >= 2. (C) 2019 Elsevier B.V. All rights reserved.