The structure of digraphs with excess one

A digraph $G$ is \emph{$k$-geodetic} if for any (not necessarily distinct) vertices $u,v$ there is at most one directed walk from $u$ to $v$ with length not exceeding $k$. The order of a $k$-geodetic digraph with minimum out-degree $d$ is bounded below by the directed Moore bound $M(d,k)=1+d+d^2+\cdots +d^k$. The Moore bound can be met only in the trivial cases $d=1$ and $k=1$, so it is of interest to look for $k$-geodetic digraphs with out-degree $d$ and smallest possible order $M(d,k)+ϵ$, where $ϵ$ is the \emph{excess} of the digraph. Miller, Miret and Sillasen recently ruled out the existence of digraphs with excess one for $k=3,4$ and $d\ge 2$ and for $k = 2$and$d \geq 8$\mathrm{.}Weconjecturethattherearenodigraphswithexcessonefor$d,k \geq 2$ and in this paper we investigate the structure of minimal counterexamples to this conjecture. We severely constrain the possible structures of the outlier function and prove the non-existence of certain digraphs with degree three and excess one, as well closing the open cases $k = 2$and$d = 3,4,5,6,7$ left by the analysis of Miller et al. We further show that there are no involutary digraphs with excess one, i.e. the outlier function of any such digraph must contain a cycle of length $\ge 3$.