ABSTRAK
Grafik bipartitmathematical equationdenganmathematical equationadalah biregular jika semua titik sudut dari setiap himpunan stabil,mathematical equationDanmathematical equation, memiliki derajat yang sama,mathematical equationDanmathematical equation, masing-masing. Makalah ini mengkaji himpunan perbedaan yang berasal dari grup Abelian dan non-Abelian. Dari himpunan tersebut, kami mengusulkan beberapa konstruksi graf bireguler bipartit dengan diametermathematical equationdan urutan optimal asimtotik untuk derajat tertentumathematical equationDanmathematical equation, yang berarti bahwa secara asimtotik orde tersebut mendekati kelipatan tetap dari batas Moore. Selain itu, kita menemukan beberapa graf biMoore, yaitu graf bireguler bipartit yang mencapai batas Moore.
1 Pendahuluan
Masalah derajat /diameter untuk graf adalah menemukan orde terbesar dari graf dengan derajat dan diameter yang ditentukan. Nilai maksimum dari angka ini adalah batas Moore , dan graf yang ordenya bertepatan dengan batas ini disebut graf Moore . Ada banyak pekerjaan yang terkait dengan topik ini (lihat survei oleh Miller dan Širáň [ 1 ]), dan juga pada subjek ini dengan beberapa batasan sehubungan dengan masalah aslinya. Salah satunya terkait dengan graf Moore bipartit. Dalam kasus ini, tujuannya adalah untuk menemukan graf bipartit reguler dengan orde maksimum dan diameter tetap. Dalam makalah ini, kami menangani masalah yang diprakarsai oleh Yebra et al. [ 2 ] pada tahun 1983, yang terdiri dari menemukan graf Moore bireguler.
Grafik bipartitmathematical equationdenganmathematical equationadalah biregular jika semua simpul dari himpunan stabilmathematical equation, untukmathematical equation, memiliki derajat yang sama. Kita menggunakan istilahpersamaan matematika-bigraf untuk menunjukkan grafik bireguler bipartit derajatpersamaan matematikaDanpersamaan matematikadan diameterpersamaan matematika; dan olehpersamaan matematika-biMoore grafik grafik bireguler bipartit dengan diameterpersamaan matematikayang mencapai batas Moore, yang dilambangkanpersamaan matematikaPerhatikan bahwa membangun grafik ini setara dengan membangun desain blok, di mana satu set partite sesuai dengan titik-titik desain blok, dan set lainnya sesuai dengan blok-blok desain. Selain itu, setiap titik berada dalam jumlah yang tetappersamaan matematikadari blok, dan ukuran setiap blok samapersamaan matematikaGrafik kejadian dari desain blok ini adalahpersamaan matematika-bigraf. Faktanya, grafik bireguler bipartit dengan derajatpersamaan matematikaDanpersamaan matematikadan partisi yang sesuai dengan ukuranpersamaan matematikaDanpersamaan matematika, memiliki diameter 3, adalah grafik Levi daripersamaan matematika-desain penutup yang sama persispersamaan matematikapadapersamaan matematikapoin denganpersamaan matematikablok ukuranpersamaan matematika, dengan properti yang desain gandapersamaan matematikajuga merupakan desain penutup.
| r\s | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 2 | 6 | ||||||||||
| 6 | |||||||||||
| 3 | 5 | 14 | |||||||||
| ∄ | 14 | ||||||||||
| 4 | 9 | 14 | 26 | ||||||||
| 9 | ◇14*◇ | 26 | |||||||||
| 5 | 7 | 16 | 27 | 42 | |||||||
| ∄ | 16* | 18 | 42 | ||||||||
| 6 | 12 | 24 | 35 | 44 | 62 | ||||||
| 12 | ◇21◇ | — | — | 62 | |||||||
| 7 | 9 | 20 | 33 | 48 | 65 | 86 | |||||
| ∄ | 20* | — | — | — | — | ||||||
| 8 | 15 | 22 | 42 | 52 | 70 | 90 | 114 | ||||
| 15 | 22* | — | — | — | — | 114 | |||||
| 9 | 11 | 32 | 39 | 56 | 80 | 96 | 119 | 146 | |||
| ∄ | 28* | — | — | — | — | — | 146 | ||||
| 10 | 18 | 26 | 49 | 69 | 88 | 102 | 126 | 152 | 182 | ||
| 18 | 26* | — | 66 | 80 | — | — | — | 182 | |||
| 11 | 13 | 28 | 45 | 64 | 85 | 108 | 133 | 160 | 189 | 222 | |
| ∄ | 28* | — | — | — | — | — | — | — | — | ||
| 12 | 21 | 40 | 60 | 68 | 99 | 114 | 145 | 175 | 198 | 230 | 266 |
| 21 | ◇35*◇ | — | — | — | — | — | — | — | — | 266 |
| s\r | 6 | 9 | 12 | 16 | 20 | 24 | 25 | 28 | 30 | 32 | 35 | 36 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 3 | 21 | 28 | ||||||||||
| 4 | — | — | 56 | 70 | 84 | 98 | — | 112 | — | 126 | — | 140 |
| 5 | — | — | — | — | 115 | — | 138 | — | 161 | — | 184 | — |
| i\j | angka 0 | 1 | 3 | 9 |
|---|---|---|---|---|
| angka 0 | angka 0 | 12 | 10 | 4 |
| 1 | 1 | angka 0 | 11 | 5 |
| 3 | 3 | 2 | angka 0 | 7 |
| 9 | 9 | 8 | 6 | angka 0 |
| Urutan | Moore | |||
|---|---|---|---|---|
| s | Γ | S | Gm(S) | terikat ( 8 ) |
| 3 | Z7 | {0,1,3} | 7(m+1) | 7(m+1) |
| 4 | Z13 | {0,1,3,9} | 13(m+1) | 14(m+1) |
| 5 | Z21 | {0,1,4,14,16} | 21(m+1) | 23(m+1) |
| 6 | Z31 | {0,1,6,18,22,29} | 31(m+1) | 34(m+1) |
| 8 | Z57 | {0,1,5,7,17,35,38,49} | 57(m+1) | 62(m+1) |
| 9 | Z73 | {0,1,17,39,41,44,48,54,62} | 73(m+1) | 79(m+1) |
| 10 | Z91 | {0,1,3,9,27,49,56,61,77,81} | 91(m+1) | 98(m+1) |
| 12 | Z133 | {0,1,3,12,20,34,38,81,88,94,104,109} | 133(m+1) |
