Enumerations of vertex orders of almost Moore digraphs with selfrepeats (Q2463473): Difference between revisions

The number \(n\) of vertices of a digraph with maximum out-degree \(d\) and diameter \(k\) cannot exceed the Moore bound \(M_{d,k}=1+d+d^2+\cdots +d^k\). It is known that except in trivial cases Moore digraphs (those with \(n=M_{d,k}\)) do not exist. The authors study almost Moore digraphs (\(n=M_{d,k}-1\)) via the notion repeat. A vertex \(v\) is called a repeat of a vertex \(u\) if there are two \(u\)-\(v\) walks of length not exceeding \(k\), which is denoted by \(r(u)=v\). The smallest positive integer \(p\) such that \(r^p(u)=u\) is called the order of \(u\). A selfrepeat is a vertex of order one. This notion has been studied in several papers (see e.g. \textit{E. T. Baskoro, Y. M. Cholily} and \textit{M. Miller} [Bull. Inst. Comb. Appl. 46, 99--109 (2006; Zbl 1099.05046)]). In this paper, an exact formula is given for the number of all vertex orders based on the vertex orders of the out-neighbours of any selfrepeat vertex.