GRAF-GRAF BERORDE n DENGAN BILANGAN KROMATIK LOKASI n - 1

YOGI, DARVIN AGUNG (2011) GRAF-GRAF BERORDE n DENGAN BILANGAN KROMATIK LOKASI n - 1. Diploma thesis, Universitas Andalas.

Text (Skripsi Fulltext) 2408201612.pdf - Published Version Restricted to Repository staff only Download (379kB)

Abstract

Misalkan c suatu pewarnaan pada graf terhubung G. Misalkan Π={C1,C2,…,Ck} adalah suatu partisi terurut dari V (G) ke dalam kelas-kelas warna yang dihasilkan. Untuk suatu titik v di G, kode warna cΠ(v) dari v adalah k-tuple terurut (d(v,C1),d(v,C2),…,d(v,Ck)), dimana d(v,Ci)=min{d(v,x)| xECi} untuk 1≤i≤k . Jika setiap titik yang berbeda di G memiliki kode warna yang berbeda terhadap Π, maka c disebut pewarnaan lokasi (locating coloring) bagi G. Bilangan kromatik lokasi XL(G) adalah minimum dari banyaknya warna pada pewarnaan lokasi di G. Hal ini menunjukkan bahwa, jika G adalah graf terhubung dengan orde n≥3 yang diinduksi oleh subgraf multipartit lengkap berorde n−1, maka n+12≤XL(G)≤n. Graf dengan orde n yang diinduksi oleh subgraf multipartit lengkap berorde n−1 digunakan untuk mengkarakterisasi graf dengan orde n≥4 yang mempunyai bilangan kromatik lokasi n−1. Selanjutnya untuk n≥5, jika G=Gn+2K2 dengan Gn adalah suatu graf multipartit lengkap berorde n−4 dan K2adalah graf lengkap berorde 2, maka G adalah graf dengan bilangan kromatik lokasi n−1. Kata kunci: Himpunan lokasi, Pewarnaan lokasi, Bilangan kromatik lokasi

Actions (login required)

View Item