On digraphs of excess one

A digraph in which, for every pair of vertices u and v (not necessarily distinct), there is at most one walk of length ≤k from u to v is called a k-geodetic digraph. The order N(d,k) of a k-geodetic digraph of minimum out-degree d fulfills N(d,k)≥1+d+d2+⋯+dk=M(d,k), where M(d,k) is the Moore bound. This bound is attained if and only if the digraph is strongly geodetic, that is, if its diameter is k. Thus, strongly geodetic digraphs only exist for d=1 or k=1. Hence, for d,k>1 we wish to determine if there exist k-geodetic digraphs with minimum out-degree d and order N(d,k)=M(d,k)+1. Such a digraph is denoted as a (d,k,1)-digraph or said to have excess 1. In this paper, we prove that (d,k,1)-digraphs are always diregular and thus that no (2,k,1)-digraphs exist. Furthermore, we study the factorization in Q[x] of the characteristic polynomial of a (d,k,1)-digraph, from which we show the non-existence of such digraphs for k=2 when d>7 and for k=3,4 when d>1.