On k-geodetic digraphs with excess one

Anita Abildgaard Sillasen


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.


k-geodetic digraph, Moore digraph, the degree/diameter problem, almost Moore digraph

Full Text:


DOI: http://dx.doi.org/10.5614/ejgta.2014.2.2.7


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats