Article Details

BILANGAN KROMATIK LOKASI DARI GRAF SIRKULAN CN (1,2,...,T)

Oleh   Fatra Maulana [20117050]
Kontributor / Dosen Pembimbing : Dr. Suhadi Wido Saputro, S.Si., M.Si.;
Jenis Koleksi : S2 - Tesis
Penerbit : FMIPA - Matematika
Fakultas : Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA)
Subjek :
Kata Kunci : graf sirkulan, pewarnaan lokasi, bilangan kromatik lokasi, partisi pembeda.
Sumber :
Staf Input/Edit : Dwi Ary Fuziastuti  
File : 1 file
Tanggal Input : 2020-09-19 11:24:11

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.