On the existence of \((d,k)\)-digraphs (Q1292845): Difference between revisions

A \((d,k)\)-digraph \(G\) is a regular digraph of degree \(d\geq 2\), diameter \(k\geq 2\) and order \(d+d^2+\cdots +d^k\) (i.e. one less than the Moore bound). There are several necessary conditions for the existence of such digraphs based on the so-called repeat permutation \(P\); see, e.g., \textit{E. T. Baskoro, M. Miller, J. Plesník}, and \textit{S. Znám} [J. Graph Theory 20, No. 3, 339-349 (1995; Zbl 0838.05054)] and \textit{E. T. Baskoro, M. Miller}, and \textit{J. Plesník} [Graphs Comb. 14, No. 2, 109-119 (1998; Zbl 0905.05033)]. The author derives several relationships between the spectrum of \(G\) and the cycle structure of \(P\) to obtain new necessary conditions. In particular, it is shown that there is exactly one \((4,2)\)-digraph, namely the line digraph of the complete digraph on 5 vertices.