A Note on Almost Moore Diagraphs of Degree Three

Edy Tri Baskoro, Mirka Miller, Josef Siran

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.


Keywords


almost Moore digraphs; degree/diameter problem; voltage assignment; cayley digraphs; graf berarah hampir Moore; masalah derajat / diameter; pemetaan voltase; grap berarah Cayley;

Full Text:

PDF

References


E.T. Baskoro, L. Brankovic, M. Miller, J. Plesnik, J. Ryan, J. Siran, Large digraphs with small diameter: A voltage assignment approach, The Journal of Combinatorial Mathematics and Combinatorial Computing 24 (1997) 161-176.

E.T. Baskoro, M. Miller, J. Plesnik and S. Znam, Regular digraphs of diameter 2 and maximum order, the Australasian Journal of Combinatorics 9 (1994) 291-306. See also Errata, 13 (1995).

E.T. Baskoro, M. Miller, J. Plesnik and S. Znam, Digraphs of degree 3 and order to close to Moore bound, Graph Theory 20 (1995) 339-349.

E.T. Baskoro, M. Miller and J. Plesnik, On the structure of digraphs with order close to the Moore bound, Graphs and Combinatorics, to appear.

E.T. Baskoro, M. Miller and J. Plesnik, Further results on almost Moore digraphs, submitted (1995).

E.T. Baskoro, On the existence of cubic digraphs with optimum order, MIHMI 3:2 (1997) 27-34.

Bridges and S. Toueg, On the impossibility of directed Moore graphs, J. Combinatorial Theory Series B29 (1980) 339-341.

J.L. Gross, Voltage graphs, Discrete Math. 9 (1974) 239-246.

J.L. Gross and T.W. Tucker, Topological Graph Theory, Wiley, New York (1987).

M. Miller, Digraph covering and its application to two optimization problem for digraphs, Australasian Journal of Combinatorics 3 (1991) 151-164.

M. Miller and I. Fris, Maximum order digraphs for diameter 2 or degree 2, Pullman volume of Graphs and Matrices, Lecture Notes in Pure and Applied Mathematics 139 (1992) 269-278.

J. Plesnik and S. Znam, Strongly geodetic directed graphs, Acta F. R. N. Univ. Comen. – Mathematica XXIX (1974) 29-34.


Refbacks

  • There are currently no refbacks.


View my Stats

Creative Commons License
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.

 

ITB Journal Publisher, LPPM ITB, Center for Research and Community Services (CRCS) Building, 6th & 7th Floor, Jalan Ganesha 10, Bandung 40132, Indonesia, Phone: +62-22-86010080, Fax.: +62-22-86010051; E-mail: jmfs@lppm.itb.ac.id