Miller, M. and Siran, J.
|DOI (Digital Object Identifier) Link:||http://doi.org/10.1016/S0012-365X(00)00134-5|
|Google Scholar:||Look up in Google Scholar|
It is well known that Moore digraphs do not exist except for trivial cases (degree one or diameter one). Consequently, for a given maximum out-degree d and a given diameter, we wish to find a digraph whose order misses the Moore bound by the smallest possible ‘defect’. For diameter two and arbitrary degree there are digraphs which miss the Moore bound by one. No examples of such digraphs of diameter at least three are known, although several necessary conditions for their existence have been obtained. In the case of degree two, it has been shown that there are no digraphs of diameter greater than two and defect one. There are five nonisomorphic digraphs of degree two, diameter two and defect two. In this paper we prove that digraphs of degree two and diameter k3 which miss the Moore bound by two do not exist.
|Item Type:||Journal Article|
|Keywords:||Directed graphs; Extremal graphs; Moore bound; Defect|
|Academic Unit/Department:||Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
|Depositing User:||Jozef Širáň|
|Date Deposited:||14 Jun 2007|
|Last Modified:||04 Oct 2016 10:02|
|Share this page:|