BILANGAN AKROMATIK PADA GRAF BINTANG, GRAF POHON PISANG DAN GRAF KEMBANG API

Darul Ihsan, Yundari, Fransiskus Fran

Abstract


Pewarnaan lengkap adalah pewarnaan simpul sehingga untuk setiap pasangan warna (a,b) terdapat sisi e=(v1,v2) sedemikian sehingga v1 diwarnai a dan v2 diwarnai b. Permasalahan yang dikaji pada pewarnaan lengkap adalah mencari bilangan akromatik yaitu maksimum banyaknya warna yang digunakan pada pewarnaan lengkap. Bilangan akromatik dinotasikan dengan lambang ѱ(G). Pada penelitian ini dibahas tentang bilangan akromatik pada graf khusus yaitu graf bintang Sn, graf pohon pisang B2,n, graf pohon pisang B3,n, graf kembang api F2,n dan graf kembang api F3,n dengan n≥3. Graf bintang Sn adalah graf dengan n+1 simpul, dengan satu simpul berdejarat n yang dinamakan simpul pusat, dan n simpul berderajat satu yang dinamakan daun. Graf Pohon pisang Bm,n adalah graf yang diperoleh dengan menghubungkan satu daun dari setiap m salinan graf bintang Sn ke sebuah simpul baru yang disebut simpul akar. Graf kembang api Fk,n adalah graf yang diperoleh dari k salinan graf bintang dengan cara menghubungkan sebuah daun dari setiap Sn melalui sebuah lintasan. Berdasarkan penelitian diperoleh bilangan akromatik pada graf bintang adalah 2. Bilangan akromatik pada graf pohon pisang B2,n dan B3,n  berturut-turut adalah 4 dan 5. Bilangan akromatik pada graf kembang api F2,n dan B3,n adalah 4 dan 5.

Kata kunci:  pewarnaan graf, pewarnaan simpul, pewarnaan lengkap.

Full Text:

PDF


DOI: http://dx.doi.org/10.26418/bbimst.v11i1.52189

Refbacks

  • There are currently no refbacks.