Bilangan Ramsey untuk Kombinasi Graf Lingkaran Terhadap Graf Roda
| Main Author: | Nurdin |
|---|---|
| Format: | Article PeerReviewed |
| Terbitan: |
Universitas Komputer Indonesia
, 2012
|
| Subjects: | |
| Online Access: |
http://repository.unikom.ac.id/1279/ http://elib.unikom.ac.id/gdl.php?mod=browse&op=read&id=jbptitbpp-gdl-s2-2001-nurdin-938-graf |
Daftar Isi:
- Diberikan dua buah graf G dan H. Bilangan Ramsey R(G,H) adalah bilangan bulat positif terkecil n sedemikian sehingga jika graf Kn diwarnai dengan warna merah dan biru maka senantiasa memuat suatu subgraf G dimana semua sisinya berwarna merah atau subgraf H dimana semua sisinya berwarna biru. Bilangan Ramsey R(G,H) dapat juga didefinisikan sebagai suatu bilangan bulat terkecil n sedemikian sehingga setiap sebarang graf F dengan n simpul akan senantiasa memuat subgraf G atau komplemen dari F akan memuat H. Huai Lu Zhou (1995) telah menunjukkan bahwa bilangan Ramsey R(Cn,Wm) = 2m 1 untuk n ganjil dan . Dalam tulisan ini akan ditunjukkan R(C5,W3) = 13. Disamping itu, kita akan menunjukkan hasil yang lebih umum untuk graf lingkaran, yakni R(C3,Cn) = 2n-1 jika . Tesis ini juga mengkaji bilangan Ramsey untuk graf berarah. Hasil yang diperoleh adalah bila dengan = dimana adalah suatu lintasan dari a ke b.