The Uniqueness of Almost Moore Digraphs with Degree 4 And Diameter 2
Rinovia Simanjuntak & Edy Tri Baskoro
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 &. 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.
Keywords: almost Moore digraph; complete digraph; line digraph; Moore bound; repeat
Begin on 10 October 2014 this website is no longer activated for article process in Journal of Mathematical and Fundamental Sciences, Journal of Engineering and Technological Sciences,
Journal of ICT Research and Applications and Journal of Visual Art and Design. The next process will be proceeded under new website at http://journals.itb.ac.id.
Download Article