On k-geodetic digraphs with excess one
Anita Abildgaard Sillasen · Electronic Journal of Graph Theory and Applications · 2014
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 .