Journal of Mathematical and Fundamental Sciences (Jan 2019)
A Note on Almost Moore Diagraphs of Degree Three
Abstract
It is well known that Moore digraphs do not exist except for trivial cases (degree 1 or diameter 1), but there are digraphs of diameter two and arbitrary degree 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. A particularly interesting necessary condition for the existence of a digraph of degree three and diameter k > 3 of order one less than the Moore bound is that the number of its arcs be divisible by k + 1. In this paper we derive a new necessary condition (in terms of cycles of the so-called repeat permutation) for the existence of such digraphs of degree three. As a consequence we obtain that a digraph of degree three and diameter k ≥ 3 which misses the Moore bound by one cannot be a Cayley digraph of an Abelian group. Catatan Untuk Keberadaan Graf Berarah Hampir Moore Derajat 3 Telah lama diketahui bahwa tidak ada graf berarah dengan orde (jumlah titiknya) sama dengan batas Moore, kecuali untuk kasus-kasus trivial, yakni untuk derajat 1 atau diameter 1; tetapi, ada graf berarah dengan diameter 2 untuk sebarang derajat dengan orde satu lebih kecil dari batas Moore. Hingga kini belum dapat ditunjukkan adanya contoh graf berarah yang sejenis dengan diameter paling sedikit 3, walaupun beberapa syarat perlu akan keberadaannya telah diberikan. Salah satu syarat perlu yang cukup menarik untuk keberadaan graf berarah dengan derajat 3, diameter k > atau = 3 dan orde satu lebih kecil dari batas Moore adalah bahwa jumlah busur yang dimilikinya harus dapat dibagi oleh bilangan k+1.
