The Uniqueness of Almost Moore Digraphs with Degree 4 And Diameter 2
Keywords:
almost Moore digraph, complete digraph, line digraph, Moore bound, repeat, batas Moore, graf berarah hampir Moore, graf berarah garis, graf berarah komplit, pengulanganAbstract
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 K4. 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.
Ketunggalan Graf Berarah Hampir Moore dengan Derajat 4 dan Diameter 2
Sari. Telah lama diketahui bahwa tidak ada graf berarah Moore dengan derajat d>1 dan diameter k>1. Lebih lanjut, untuk derajat 2 dan 3, telah ditunjukkan bahwa untuk diameter t>3, tidak ada graf berarah Hampir Moore, yakni graf berarah teratur dengan orde satu lebih kecil dari batas Moore. Graf berarah dengan orde mendekati batas Moore digunakan dalam pcngkonstruksian jaringan optimal. Untuk diameter 2, diketahui bahwa graf berarah Hampir Moore ada untuk setiap derajat karena graf berarah garis (line digraph) dari graf komplit adalah salah satu contoh dari graf berarah tersebut. Akan tetapi, belum dapat dibuktikan apakah graf berarah tersebut merupakan satu-satunya contoh dari graf berarah Hampir Moore tadi. Selanjutnya telah ditunjukkan bahwa untuk derajat 3, tidak ada graf berarah Hampir Moore diameter 2 selain graf berarah garis dari K4. Pada makalah ini, kita mengkaji graf berarah Hampir Moore diameter 2 dan derajat 4. Kita buktikan bahwa ada tepat satu graf berarah tersebut, yaitu graf berarah garis dari K5.
References
Baskoro, E.T., Miller, M., Siran, J., & Sutton, M., Complete characterization of almost Moore digraphs of degree three, J. Graph Theory (in press).
Baskoro, E.T., Miller, M., Plesnik, J., & Znam, S., Digraphs of degree 3 and order close to the Moore bound, J. Graph Theory 20, 339-349 (1995).
Baskoro, E.T., Miller, M., Plesnik, J., & Znam, S., Regular digraphs of diameter 2 and maximum order, The Australasian Journal of Combinatorics 9 (1994) 291-306. See also Errata 13 (1995).
Bermond, J.C., Delorme, C., & Quisquater, J., Strategies for interconnection networks: some methods from graph theory, Journal of Parraliel and Distributed Computing 3, 433-449 (1986).
Bridges, W.G. & Toueg, S., On the impossibility of directed Moore graphs, J. Combinatorial Theory 29, 339-341 (1980).
Fiol, M.A., Alegree, I., & Yebra, J.L.A., Line digraphiteration and the (d,k) problem for directed graphs. Proc. 10th Symp. Comp. Architecture, Stocholm (1983) 174-177.
Gimbert, J., On the existence of (d,k)-digraphs, Discrete Math 197/198, 375-391 (1999).
Iswadi, H. & Baskoro, E.T., On (4,2)-digraphs with containing a cycle of length 2, J. Malaysian Math Soc. (in press).
Hoffman, J. & Singleton, R.R., On Moore graphs with diameter 2 and 3, IBM J. Res Develop. 4 497-504 (1960).
Imase, M. & Itoh, M., Design to minimize diameter on building-block network, IEEE Trans. On Computers C-32 782-784 (1983).
Miller, M. & Fris, I., Maximum order digraphs for diameter 2 or degree 2, Pullman vol. of Graphs and Matrices, Lecture Notes in Pure and Applied Mathematics 139, 269-278 (1992).
Miller, M. & Fris, I., Minimun diameter of diregular digraphs of degree 2, Computer J. 31, 71-75 (1988).
Plesnik, J. & Znam, S., Strongly geodetie directed graphs, Acta Fac. Rer. Nat. Univ. Comen., Mathematica 29, 29-34 (1974).
