Digraphs of degree two which miss the Moore bound by two

Miller, M. and Siran, J. (2001). Digraphs of degree two which miss the Moore bound by two. Discrete Mathematics, 226(1-3) pp. 269–280.

DOI: https://doi.org/10.1016/S0012-365X(00)00134-5

Abstract

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.

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI

About

• Item ORO ID
• 8105
• Item Type
• Journal Item
• ISSN
• 0012-365X
• Keywords
• Directed graphs; Extremal graphs; Moore bound; Defect
• Academic Unit or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
  Faculty of Science, Technology, Engineering and Mathematics (STEM)
• Depositing User
• Jozef Širáň