The Uniqueness of Almost Moore Digraphs with Degree 4 And Diameter 2 - Rinovia Simanjuntak; Edy Tri Baskoro (Journal of Mathematical and Fundamental Sciences, 2019)
Abstract. It is well known that Moore digraphs of degree d > 1 and diameter k > 1 do not exist. For degrees 2 and 3, it has been shown that for diameter k â‰¥ 3 there are no almost Moore digraphs, i.e. the diregular digraphs of order one less than the Moore bound. Digraphs with order close to the Moore bound arise in the construction of optimal networks. For diameter 2, it is known that almost Moore digraphs exist for any degree because the line digraphs of complete digraphs are examples of such digraphs. However, it is not known whether these are the only almost Moore digraphs. It is shown that for degree 3, there are no almost Moore digraphs of diameter 2 other than the line digraph of K4. In this paper, we shall consider the almost Moore digraphs of diameter 2 and degree 4. We prove that there is exactly one such digraph, namely the line digraph of K5.