Vol.14, No. 2,  149-153,  Januari  2018
Bilangan Ramsey untuk Graf Bintang Genap Terhadap Roda Genap
Hasmawati 

## Abstrak
Untuk  sebarang  graf G dan H ,  bilangan  Ramsey R ( G,H )  adalah  bilangan  asli  terkecil n sedemikian sehingga sebarang graf F yang berorde n memenuhi kondisi berikut: F memuat G atau komplemen F memuat H . Dalam makalah ini dikaji bilangan Ramsey R ( G,H ), dimana G adalah graf bintang S n dan H adalah graf roda W m .  Kami akan menunjukkan bahwa R ( S 4 ,W 6 )= 9  dan untuk n = 6, 8,  maka R ( S n ,W m ) =  2 n +1 untuk m = n .
Kata Kunci: Bilangan Ramsey, Graf Bintang, Graf Roda.

## Abstract
For given graphs G dan H , the Ramsey number R ( G,H ) is the smallest natural number n such that for every graph F of order n: either F contains G or the complement of F contains H . This paper investigates the Ramsey numbers R ( G,H ), where G is a stars S n and H is   wheels W m . We show that R ( S 4 ,W 6 )= 9  and  for n =4, 6, 8  then R ( S n ,W m ) =  2 n +1 for m = n .
Keywords : Ramsey Number, Star Graph, Wheel Graph.

## 1. Pendahuluan
Graf G ( V,E) adalah  suatu  sistem  yang  terdiri  dari  himpunan  titik  berhingga  tak  kosong V=V ( G ) dan himpunan sisi E=E ( G ) yaitu himpunan pasangan tak terurut dari anggota-anggota V. Jika V ( G )  mempunyai  anggota  sebanyak n, maka  graf G dikatakan berorde  n dan  dinotasikan . G n  Jika u,v  V ( G )  dan e=uv  E ( G ),  maka u disebut tetangga dari v, demikian  pula sebaliknya.
Graf G dengan n titik  dan  setiap  dua  titiknya  bertetangga  disebut  graf lengkap, dinotasikan dengan K n . Graf F disebut komplemen dari graf G bila V ( F ) =V ( G ) dan uv  E ( F )  jika dan hanya jika uv  E ( G ). Komplemen dari graf G dinotasikan dengan G . Graf H disebut subgraf dari G jika V ( H )  V ( G )  dan E ( H )  E ( G ). Himpunan titik V pada graf G disebut himpunan titik bebas jika  setiap  dua  titik  di V tidak  bertetangga. Notasi 0 ( ) G  menyatakan  banyaknya  titik pada himpunan  titik  bebas  maksimal di G .  Suatu  graf G dikatakan bipartit jika V ( G )  dapat dipartisi kedalam dua subhimpunan tak kosong V 1 dan V 2 , sedemikian sehingga untuk setiap sisi e=uv  E ( G ),  berlaku u  V 1 dan v  V 2 atau v  V 1 dan u  V 2 .  Misalkan G adalah  graf  bipartit dengan 1 V = n dan 2 V = m .  Graf G dikatakan bipartit lengkap dan  dinotasikan K n,m , jika  setiap titik u  V 1 dan v  V 2 terdapat sisi e= uv  E ( G ).
Misalkan G 1 adalah graf dengan himpunan titik V 1 dan himpunan sisi E 1 , serta G 2 adalah graf  dengan  himpunan  titik V 2 dan  himpunan  sisi E 2 ,  graf  gabungan G = G 1 + G 2 adalah  graf
 Jurusan Matematika FMIPA Universitas Hasanuddin Makassar
Hasmawati
dengan  himpunan  titik V ( G )  = V 1  V 2 dan  himpunan  sisi E ( G )  = E 1  E 2  { uv : u  V 1 , v  V 2 }. Misalkan G adalah suatu graf dengan himpunan titik V ( G )= v 1 , v 2 , ..., v n dan x=v i v j  E ( G ) untuk  suatu i,j  {1,2,  ..., n }.  Graf G’ := G + x adalah  suatu    graf  baru  dengan  himpunan  titik V ( G’ )= V ( G ) dan himpunan sisi E ( G’ )= E ( G )  { x }. Jalan dari u ke v dengan panjang k pada graf G ( V,E ) adalah suatu subgraf dengan barisan titik u=u 0 ,u 1, ...,u k dimana ( u 1 u i+1 )  E (G) untuk i= 1 , 2 ,...,k- 1. Lintasan P n adalah jalan dengan n titik yang setiap titiknya berbeda. Suatu graf dikatakan terhubung jika untuk setiap dua titik u dan v dari graf tersebut terdapat suatu lintasan dari u ke v. Komponen dari suatu graf  adalah  subgraf terhubung maksimal dari graf tersebut. Jika P n adalah suatu lintasan dengan barisan titik v 1 , v 2 , ..., v n dan n  3. maka graf C n := P n + v 1 v n disebut s iklus dengan n titik.  Graf pohon T n (tree) adalah graf terhubung dengan n titik yang tidak memuat siklus. Graf roda W k (wheel) dengan k +1 titik adalah  graf C k +K 1 .  Titik x  V ( K 1 )  disebut  titik  pusat  roda  (hub)  dan  siklus C k disebut rim dari roda.    Graf 1 n K  + K 1 disebut  graf bintang (star)    dengan n titik,    dan  dinotasikan S n .  Titik x  V ( K 1 ) disebut sebagai titik pusat (center) graf bintang (Gambar 1).
Gambar 1. a) graf pohon, b) graf bintang,
c) graf lengkap, dan d) graf roda.
Panjang  siklus  terbesar  pada  suatu  graf G dinotasikan  dengan c ( G ),  sedangkan  panjang siklus terkecil dinotasikan dengan g ( G ). Graf G dengan orde n disebut pancyklic jika G memuat semua siklus C l dengan 3  l  n , dan disebut pancyklic lema jika G memuat C h dengan g ( G )  h  c ( G ).  Misalkan G ( V,E )  adalah  sebarang  graf  sederhana  dan k adalah  sebarang  bilangan  asli.
Graf G disebut  terhubung- k jika G > k dan G-X terhubung  untuk  setiap X  V  E dengan . k X  Keterhubungan k G  ) (  adalah bilangan bulat terbesar k sehingga G merupakan graf terhubung- k. Berikut ini disajikan tiga lema dimana ketiga lema ini digunakan dalam pembuktian hasil-hasil pada penelitian ini.

## Lemma 1. (Lemma Bondy)
Misalkan G adalah graf berorde n. Jika
2 ) ( n G   , maka G adalah pansiklis atau
2 , 2 n n K untuk n genap.
a) T 7 c) K 4
b) S 6
d) W 6

## Hasmawati
Bilangan Ramsey R ( G,H ) untuk sebarang graf G dan graf H adalah bilangan asli terkecil n sedemikian  sehingga  untuk  setiap  graf F dengan n titik  memenuhi  kondisi: F memuat G atau F memuat H .  Misalkan F berorde n tidak memuat G dan F tidak memuat H . Jika sebarang graf dengan orde n +1 senantiasa memuat G atau komplemennya memuat H , maka F disebut graf kritis untuk G dan H. Bilangan kromatik  ( H ) adalah bilangan asli terkecil k sehingga jika titik- titik  pada H dapat  diwarnai  dengan k warna  maka    setiap  dua  titik  yang  bertetangga    pada H mempunyai warna berbeda. Chvatal dan Harary (1972) memberikan batas bawah untuk R ( G,H ), yaitu R ( G,H )  (  ( H )-1)( c ( G )-1)+1,  dimana c ( G )  adalah  banyaknya  titik  pada  komponen terbesar G. Berdasarkan batas bawah Chvatal dan Harary ini diperoleh:
 Batas bawah untuk R ( S n , W m )  dimana n  3 dan m ganjil adalah  3 n – 2.
 Batas bawah untuk R ( S n , W m )  dimana n  3 dan m genap adalah  2 n – 1.  Batas bawah untuk R ( T n , K m ) dimana n dan m sembarang adalah ( m -1)( n –1)+1.
Beberapa  bilangan  Ramsey  yang  telah  dihasilkan  antara  lain  dalam  Burr et  al. (1975) yang    membuktikan  bahwa km+l n  – min ( mi,nj ) – 1  R ( mG,nH )  km+ln  -min(mi,nj ) +C , dimana G k  , H l  , i =  0 ( G ) dan j =  0 ( H ). Dalam Baskoro (2002) telah dibuktikan bahwa jika n  3, maka R ( S n ,W 5 ) = 3 n -2. Chen et al. menunjukkan bahwa jika n  m -1  2 dan m ganjil maka R ( S n ,W m ) = 3 n -2. Dalam Hasmawati (2004) diperoleh R ( S n ,W m ) = m+n -2 untuk n ganjil dan m genap, R ( S n ,W m ) = m+n -1 untuk  yang lainnya.
Dalam  Korolova  (2004)  diperoleh    hasil  yang  lebih  baik  untuk  bintang  genap  terhadap roda genap. Hasilnya dituliskan dalam teorema berikut.
Teorema 1. Jika m genap dan m  n, maka R(S n ,W m )  2n-1.

## 2. Hasil Utama
Pasal  ini  menyajikan  dua  hasil  utama  yang  dituliskan  dalam  bentuk  teorema.  Penyajian teorema langsung disertai dengan bukti.
Teorema 2. R ( S 4 ,W 6 ) = 9.
Bukti:
Pandang graf 5 3 C K F   . Graf ini berorde 8 dan tidak memuat W 6 . Sedangkan graf F adalah graf  2-reguler  yang  berarti  tidak  memuat S 4 .  Jadi  graf F adalah  graf  kritis  untuk S 4 dan W 6 . Dengan demikian diperoleh R ( S 4 ,W 6 )  9.
Gambar 2. Graf 5 3 C K F   .
Berikutnya  akan  ditunjukkan  bahwa  bilangan  Ramsey R ( S 4 ,W 6 )  9.  Ambil  sebarang  graf 1 F dengan 1 F = 9. Andaikan 1 F tidak memuat S 4 .  Akan ditunjukkan 1 F memuat W 6 . Karena 1 F tidak  memuat S 4 maka  untuk  setiap  titik  di 1 F mempunyai  derajat  paling  tinggi  2.  Ambil sembarang titik di 1 F sebut x . Tulis ] [ \ ) ( 1 x N F V A  dan T adalah subgraf 1 F yang diinduksi oleh A .  Berarti T = 9 ] [ ) ( 1    x
N F V A -3=6  dan  setiap  titik T berderajat T -3  3.
Nilai  ini  lebih  besar  atau  sama  dengan 2 T menurut  Lemma  1 T memuat  semua  siklus C l dengan l = 3, 4, 5, dan 6. Berarti T memuat C 6 . Titik x bersama-sama C 6 membentuk W 6 di 1 F . Jadi diperoleh 1 F memuat S 4 atau 1 F memuat W 6 . Karenanya diperoleh R ( S 4 W 6 )  9.   Dari kedua ketidaksamaan di atas disimpulkan R (S 4, W 6 ) = 9.
Teorema 2.
R(S n ,W m )= 2n+1  untuk m = n dengan n genap dan n > 4.
Bukti:
Pandang F dengan  graf n F 2  .  Bagi  himpunan  titik ) ( F V kedalam  dua  kelompok  sebut A dan B . Labeli titik di A dengan a 1 , a 2 , ... , a 2 k -1 dan titik-titik di B dengan b 1 , b 2 , ..., b 2k+1 dengan n =2 k .  Subgraf dari F yang diinduksi oleh A (   A F ) isomorf dengan K 2 k -1 dan subgraf dari F (   B F )  yang  diinduksi  oleh  B (   B F ),  komplemennya  isomorf  dengan  siklus C 2 k +1 .    Berarti   B F adalah subgraf yang setiap titiknya berderajat 2 k -2 = n -2. Ini artinya graf F adalah graf ( n - 2)-reguler dan terdiri dari dua komponen. Dengan demikian F tidak memuat S n untuk n = 6, 8 . Mudah diperiksa bahwa
1 1
    n n C K F untuk n = 6, 8 . Jadi  Graf F memuat W n +1 tetapi tidak memuat W n .  Jadi  graf F adalah  graf  kritis  untuk S n dan W m untuk n=m .  Dengan  demikian diperoleh R ( S n ,W m )  2 n +1 untuk n=m .
K 3 C 5 KK 5 3 C K F  

## Hasmawati
Berikutnya  akan  ditunjukkan  bahwa  bilangan  Ramsey R ( S n ,W m )  2 n +1.  Ambil sebarang  graf 1 F dengan 1 F =  2 n +1.  Andaikan 1 F tidak  memuat S n .    Akan  ditunjukkan 1 F memuat W m .  Karena 1 F tidak  memuat S n maka  untuk  setiap  titik  di 1 F mempunyai  derajat paling  besar n -2.  Ambil  sembarang  titik  di 1 F sebut x .  Tulis ] [ \ ) ( 1 x N F V A  dan T adalah subgraf 1 F yang diinduksi oleh A . Berarti T n x N F V 2 ] [ ) ( 1    +1-( n -2+1)= n +2 dan setiap  titik T berderajat T -( n -3)  3.  Untuk n =  6,  nilai  ini  lebih  besar  atau  sama  dengan 2 T
menurut Lemma 1 T memuat semua siklus C l dengan l = 3, 4, 5, dan 6. Berarti T memuat C 6 . Titik x bersama-sama C 6 membentuk W 6 di 1 F . Jadi diperoleh 1 F memuat S 6 atau 1 F memuat W 6 . Karenanya diperoleh R ( S n W m )  2 n +1.  Untuk n = 8, nilai ini lebih kecil dari 2 T . Karena itu Lemma Bondy tidak dapat digunakan.

## 3. Kesimpulan
Bilangan  Ramsey    untuk  kombinasi  graf  bintang  dan  graf  roda R ( S n ,W m )  dengan n genap  dan n <  8,  Lemma  Bondy  masih  dapat  dimanfaatkan.  Namun  untuk n  8,  Lemma  bondy tidak dapat lagi digunakan. Perlu syarat cukup atau syarat perlu yang lain yang dapat digunakan dalam pembuktiannya.

## Daftar Pustaka
[1] Baskoro, E. T., Surahmat, Nababan, S. M.  dan Miller, M., 2002, On Ramsey Numbers for Tree versus Wheels of Five or Six vertices, Graph Combin. , 18: 717-721.
[2] Burr,  S.  A.,  Erdos,  P.,  dan  Spencer,  J.  H.,  1975,  Ramsey  numbers  for  multiple  copies  of graphs, Trans. Amer. Math. Soc. , 2009.
[3] Chen, Y. J., Zhang, Y. Q., dan Zhang, K. M.,  The Ramsey Number of Stars versus Whells, Discrete Math. , to appear.
[4] Chvatal,  V.,  Harary,  F.,  1972,  Generalized  Ramsey  Theory  for  Graph,  III:Small  off- Diagonal Numbers, Pac. J. Math. , 41, 335-345.
[5] Hasmawati,  2004,  Bilangan  Ramsey  untuk  kombinasi  Graf  Bintang  terhadap  Graf  Roda, Tesis Magister , Departemen Matematika ITB.
[6] Korolova,  A.,  2004,  Ramsey  Numbers  of  versus  Whell  of  similar  sizes, Discrete  Math. , 292, 107-117.