On the existence of (d,k)-digraphs Original Research Article

A (d,k)-digraph is a regular directed graph of degree d > 1, diameter k > 1, and order one less than the (unattained) Moore bound. If G is a (d,k)- digraph, then for each vertex v ϵ V(G) there exists only one vertex, denoted by r(v) and called the repeat of v, such that there are exactly two v → r(v) walks of length less than or equal to k. The map r, which assigns to each vertex v ϵ V(G) the vertex r(v), is an automorphism of G, and its associated permutation matrix P satisfies the equation I + A + … + Ak = J + P, where A is the adjacency matrix of G and J denotes the all-ones matrix. From this equation a close relationship between the spectrum of G and the cycle structure of the permutation r is derived. We use the characteristic polynomial of a (d,k)-digraph to obtain some new necessary conditions for the cycle structure of the automorphism r of such a digraph. In particular, we apply these results to the study of the existence of the (d,k)- digraphs in the cases k = 2,3. Finally, we prove that there is exactly one (4,2)-digraph, namely the line digraph of K5.