Batas Bawah Bilangan Ramsey pada Graf Bintang S_10 Versus Roda W_12 Lower Bound of the Ramsey Number for the Star Graph S_10 Versus Wheels W_12

Hamdana hadaming, Andi Ardhila Wahyudi

Abstract


Bilangan Ramsey untuk graf  terhadap graf , dinotasikan dengan  adalah bilangan bulat terkecil  sedemikian sehingga untuk setiap graf  dengan orde akan memenuhi sifat berikut:  memuat graf  atau komplemen dari  memuat graf .Penelitian ini bertujuan untuk  menentukan graf kritis maksimum  dan  dengan genap. Berdasarkan batas bawah tersebut di tentukan batas atas minimum sehingga diperoleh nilai bilangan Ramsey untuk graf bintang  versus , atau . Dengan demikian penentuan batas bawah bilangan Ramsey  dilakukan dengan cara batas bawah yang  diberikan oleh Chavatal dan Harary, untuk bilangan Ramsey pada graf bintang  versus  adalah , dengan  adalah bilangan kromatik titik graf roda  dan  adalah kardinalitas komponen terbesar graf . Berdasarkan batas bawah Chavatal dan Harary tersebut dikonstruksi graf kritis untuk  dan  yang ordenya lebih besar dari nilai batas bawah yang diberikan Chavatal dan Harary. Orde dari graf kritis tersebut merupakan batas bawah terbaik untuk .

 

Kata kunci: Bilangan Ramsey, bintang, roda

 

Abstract

Ramsey Numbers for a graph  to a graph , denoted by   is the smallest integer n such that for every graph  of order  either  the following meeet:  contains a graph  or the complement of  contains the graph . This aims of the study to determine the maximum critical graph  and . Based on the lower bound of the specified minimum upper bound in order to obtain numerical values for the Ramsey graph  Star versus  , or . Thus the determination of Ramsey numbers .  is done by determine the lower boundary and upper bound. The lower bound given by Chavatal and Harary, for ramsey number for star graph versus wheel   is , is a point graph of chromatic number wheel  and  is the cardinality of the largest component of the graph . Based on the lower bound Chavatal and Harary graph is constructed critical to  and  are poin greater than the lower bound value given Chavatal and Harary. Order of the critical graph is the best lower bound for .

 

Keywords : Ramsey number, Stars, and Wheels


Full Text:

PDF

References


Ahsan. (2010). Bilangan Ramsey untuk Graf Bintang Terhadap Roda Berorde Sembilan. (Tesis). Makassar: Universitas Hasanuddin.

Chavatal, V., dan Harary, F. (1972). Generalized Ramsey theory for graphs, III, small off-diagonal numbers, Pac. J. Math., 41, 335 - 345.

Chen, Y. J., Zhang, Y .Q., dan Zhang, K. M. (2004). The Ramsey numbers of stars versus wheels, European J. Combin., 25, 1067 - 1075.

Hasmawati. (2007). Bilangan Ramsey untuk Graf Gabungan Bintang. (Disertasi): Departemen Matematika ITB.

Korolova, A. (2005). Ramsey numbers of stars versus wheels of similar sizes, Discrete Math., 292, 107 - 117.

Zhang, Y. Q., dan Zhang, K. M. (2004). On Ramsey numbers R(Sn;W8) forsmall n, Department of Mathematics, Nanjing University, China. Preprint.




DOI: https://doi.org/10.26618/jkpd.v3i1.1177

Refbacks

  • There are currently no refbacks.


Copyright (c) 2018 Hamdana hadaming, Andi Ardhila Wahyudi

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.