Boxicity pada Graf roda(Wn), Graf helm(Hn), Graf helm tertutup(cHn) dan Graf sikel berambut(hCn)

ABSTRAK

Graf G adalah suatu himpunan tak kosong berhingga dari objek yang disebut titik-titik bersama dengan himpunan (mungkin kosong) dari pasangan tak berurutan titik-titik yang berbeda di G yang disebut sisi. Boxicity pada graf G, dinotasikan sebagai box(G), adalah bilangan bulat positif terkecil k sehingga dapat digambarkan sebagai perpotongan pada k-box. k-box adalah himpunan dari titik-titik R_1 X R_2 X R_3 X ... R_k yang dapat diartikan sebagai "ruang dimensi-k". Jadi boxcity adalah dimensi terkecil k, demikian sehingga G dapat digambarkan sebagai intersection graph pada ruang di ruang dimensi-k. Skripsi ini membahas tentang boxcity pada graf roda (Wn), graf helm (Hn), graf helm tertutup (cHn), dan graf sikel berambut (hCn).

Berdasarkan hasil pembahasan, diperoleh boxcity graf roda (Wn), graf helm (Hn), graf helm tertutup (cHn), dan graf sikel berambut (hCn) sebagai berikut :
1. Graf Roda
Boxcity pada graf Roda yaitu :
a) box(W_3)=1,
b) box(Wn)=2, untuk n>3
2. Graf Helm
Boxcity pada graf helm (Hn) adalah 2, untuk n≥3
3. Garf Helm Tertutup
Boxcity pada graf helm tertutup (cHn) adalah 2, untuk n≥3
4. Graf Sikel Berambut
Boxcity pada graf sikel berambut (hCn) adalah 2,untuk n≥3