Perpustakaan Digital ITB

Abstrak: Telah kita ketahui bahwa tidak terdapat graf berarah Moore dengan derajat d > 1 dan diameter k > 1. Untuk derajat 2 dan 3 telah dibuktikan bahwa untuk diameter k > 3 tidak terdapat graf almost Moore, yaitu graf berarah diregular dengan orde batas Moore dikurangi satu. Sedangkan untuk diameter 2 dan derajat sebarang, terdapat graf almost Moore. Salah satu contohnya adalah graf garis berarah dari graf komplit. Khususnya untuk derajat 3, telah ditunjukkan bahwa graf garis berarah dari K4 adalah satu-satunya graf almost Moore. Walaupun demikian, untuk derajat k > 3 belum diketahui apakah graf tersebut merupakan satu-satunya graf almost Moore. Dalam tesis ini, dibahas graf almost Moore dengan diameter 2 dan derajat 4. Akan ditunjukkan bahwa graf tersebut tunggal, yaitu graf garis berarah dari K4.