On k-geodetic digraphs with excess one

Abstract

A k-geodetic digraph G is a digraph in which, for every pair of vertices u and v (not necessarily distinct), there is at most one walk of length at most k from u to v. If the diameter of G is k, we say that G is strongly geodetic. Let N(d,k) be the smallest possible order for a k-geodetic digraph of minimum out-degree d, then N(d,k) is at most 1+d+d^2+...+d^k=M(d,k), where M(d,k) is the Moore bound obtained if and only if G is strongly geodetic. Thus strongly geodetic digraphs only exist for d=1 or k=1, hence for d,k >1 we wish to determine if N(d,k)=M(d,k)+1 is possible. A k-geodetic digraph with minimum out-degree d and order M(d,k)+1 is denoted as a (d,k,1)-digraph or said to have excess 1.In this paper we will prove that a (d,k,1)-digraph is always out-regular and that if it is not in-regular, then it must have 2 vertices of in-degree less than d, d vertices of in-degree d+1 and the remaining vertices will have in-degree d.Furthermore we will prove there exist no (2,2,1)-digraphs and no diregular (2,k,1)-digraphs for k> 2.