Struktur keteraturan (d, k, 2) - digraph , untuk d 3, dan k 2

Struktur keteraturan (d, k, 2) - digraph , untuk d 3, dan k 2
Lemma 2.4.2.a.1 (Dafik, Miller,Costas Iliopoulus, dan Zdenek Ryjacek; Slamin)
Jika G graf berarah kurang dua dari batas Moore dengan out-degree d 3, diameter k 2, dan S adalah himpunan semua titik di G yang in-degreenya kurang dari d, maka , untuk setiap titik u V(G)
Bukti :
Misalkan v S, ambil sebarang titik u V(G) dengan u v. Misalkan pula = { u1, u2, ..., ud}. Karena diameter G adalah k, maka titik v harus terdapat di masing-masing himpunan , i = 1, 2, ..., d. Sehingga untuk masing-masing i, ada titik xi {u} sedemikian hingga xiv adalah sisi berarah dari G. Karena in-degree dari v kurang dari d, maka setiap xi tidak berbeda semua. Akibatnya, ada beberapa titik yang paling sedikit terdapat dua kali di . Sehingga sebuah titik harus menjadi repeat dari u. Karena G adalah graf berarah defect dua, maka ada dua titik yang merupakan repeat dari u, yaitu r1(u) dan r2(u). Oleh karenanya .

Corollary 2.4.2.a.1

Lemma 2.4.2.a.2 (Dafik, Miller,Costas Iliopoulus, dan Zdenek Ryjacek)
Diketahui G adalah graf berarah kurang dua dari batas Moore dengan out-degree d 3 dan diameter k 2. S adalah himpunan semua titik di G yang in-degree-nya kurang dari d, jika v1 S maka = d – 1
Bukti :
Misalkan v S, ambil sebarang titik u V(G) dengan u v. Misalkan pula = { u1, u2, ..., ud}. Karena diameter G adalah k, maka titik v harus terdapat di masing-masing himpunan , i = 1, 2, ..., d. Sehingga untuk masing-masing i, ada titik xi {u} sedemikian hingga xiv adalah sisi berarah dari G. Jika d - 2, maka berdasarkan lemma 2.4.2.a.1, in-excess-nya harus memenuhi :

Perhatikan banyaknya titik di multiset . Untuk mencapai v1 dari semua titik di G, maka banyaknya titik yang berbeda di harus :

dengan 2 t k dan + + ... + . Jika = d – 2 maka = d - 2. Dengan mengambil = 2d, dan = 0 untuk 3 t k, maka :

= 1 + (d-2) + (d(d-2) + ) + (d(d(d-2) + )+ ) (1 + d + ... + )
= 1 + (d-2) + (d(d-2)+2d) + (d(d(d-2)+2d)) (1 + d + ... + )
= 1 + d-2 + + ( 1 + d + ... + )
= Md,k – 2
Karena = 2d, = 0 untuk 3 t k, dan G memiliki sebuah titik dengan in-degree d – 2, diketahui = d, misalkan S = { v1,v2, v3, ..., vd}. Setiap vi untuk i = 2, 3, 4, ..., d, harus mencapai v1 dengan jarak maksimal k. Karena v1 dan setiap vi memiliki in-neighbourhood yang sama, maka v1 adalah self repeat. Hal ini mengakibatkan v1 terdapat dua kali di multiset . Sehingga < Md,k– 2. Hal ini kontra diksi dengan yang diketahui bahwa G adalah graf berarah defect dua. Oleh karenanya, = d – 1 untuk sebarang vi S.
Lemma 2.4.2.a.3 (Dafik, Miller,Costas Iliopoulus, dan Zdenek Ryjacek)
Jika S adalah himpunan semua titik di G yang in-degree-nya adalah d – 1 maka d
Lemma 2.4.2.a.4 (Dafik, Miller,Costas Iliopoulus, dan Zdenek Ryjacek)
Setiap (d, k, 2) – digraph adalah out-regular dan almost in-regular untuk d 3 dan k 2. Jika k = 2 maka d-1 d dan jika k 3 maka = d
Bukti :
Berdasarkan teorema 2.4.2 telah dibuktikan bahwa (d,k,2) adalah our- regular. Akan dibuktikan bahwa setiap (d,k,2) – digraph adalah almost diregular.Jika S = maka (d,k,2)- digraph adalah diregular. Dengan lemma 2.4.2.a.2; jika S maka semua titik di S mempunyai in-degree d-1, sehingga

Ambil sebarang v S, maka = d-1. Karena diameter G adalah k, maka gabungan semua himpunan untuk 0 t k adalah semua himpunan titik V(G) di G. Akibatnya :

untuk memperkirakan penjumlahan diatas, observasi bahwa :

dengan 2 t k dan + + ... + . Dengan mengambil = =, dan = 0 untuk 3 t k. persamaan terakhir akan sama jika mengasumsikan bahwa semua titik dari S – {v} terdapat di dan semua titik S’ anggota . Sehingga :

= 1 + (d-1) + (d(d-1) + ) + (d(d(d-1) + )+ ) (1 + d + ... + )
= 1 + (d-1) + (d(d-1)+ ) + (d(d(d-1)+ )) (1 + d + ... + )
= d + +...+ +( -d)( 1 + d + ... + )
= Md,k – 2 + ( -d)( 1 + d + ... + )+1
Tetapi G adalah graf berarah defect dua dengan orde Md,k – 2, akibatnya ;
( -d) +1 0
d -
Jika k = 2 dan d 3 maka d – 1. Karena 1 d akibatnya d-1 d. Jika k 3 dan d 3 maka d karena 0< < 1. Hal ini mengakibatkan = d. Diantara kasus d-1 d untuk k = 2 dan = d. untuk k 3 , dapat dikatakan bahwa graf berarah tersebut almost in-regular digraph