Graphs of order two less than the Moore bound (Q924968)

The degree/diameter problem asks to determine the largest order \(n_{d,k}\) of a graph of maximum degree at most \(d\) and diameter at most \(k\). It is well known that for \(d\geq 3\) and \(k\geq 3\) the known Moore bound \(M_{d,k}=1+d+d(d-1)+\cdots +d(d-1)^{k-1}\) cannot be attained. In this paper graphs of order \(M_{d,k}- 2\) are studied. The results make use of the notion of a repeat. The main result says that if \(d=4\) and \(k\geq 3\) then there are no such graphs.