Digraphs with degree two and excess two are diregular

Abstract

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\ge 2$.

Revised version

Cited by in corpus (1)

• On diregular digraphs with degree two and excess three