Perpustakaan Digital ITB

Misalkan ???? merupakan pewarnaan-???? dari graf terhubung ???? dan misalkan ?= ????1,????2,…,????_???? merupakan partisi dari ???? ???? yang diinduksi oleh ????. Kode dari ????????? adalah ????-tuple ????? ???? = ???? ????,????1 ,???? ????,????2 ,…,???? ????,???????? dimana ???? ????,???????? =???????????? ???? ????,???? :????????????? untuk 1??????????. Jika setiap dua titik berbeda di ???? memiliki kode yang berbeda, maka ???? disebut pewarnaan lokasi dari ????. Pewarnaan lokasi ???? dengan warna paling sedikit disebut pewarnaan lokasi minimum dan banyaknya warna yang digunakan disebut bilangan kromatik lokasi dengan notasi ???????? ???? . Pada tugas akhir ini akan dikaji bilangan kromatik lokasi dari graf sirkulan ????????(1,2,…,????) dengan orde ?????3 dan ?????1. Ghanem dkk [Locating Chromatic Number of Powers of Paths and Cycles, Symmetry 11 (2019), 389], membuktikan bahwa 1. Jika ?????2????+3,?????1 mod ????+1 , maka ????????(????????(1,2,…,????))=????+3, 2. Jika ?????2????+3,?????6,????????? mod ????+1 dan ????? 2, ?????32 , maka ????????(????????(1,2,…,????)) ?????+2+????, 3. Jika ?????2????+3,?????4,????? ????2 mod ????+1 , maka ????????(????????(1,2,…,????))?????+ ????+12 . Setelah dikaji ulang, ditemukan bukti penyangkal untuk (1), (2), dan (3). Batas atas dan batas bawah yang tepat untuk graf sirkulan secara umum akan diberikan. Selain itu, akan dibuktikan bahwa batas-batas tersebut tajam. Untuk graf sirkulan dengan orde cukup besar, nilai eksak dari bilangan kromatik lokasi dari graf sirkulan tersebut dapat ditentukan.