Perpustakaan Digital ITB

Fibonacene merupakan rantai hidrokarbon benzenoid tanpa titik internal yang semua heksagon nonterminalnya adalah angularly annelated. Suatu heksagon dikatakan angularly annelated jika heksagon bertetangga dengan tepat dua heksagon lainnya dan memiliki dua titik berderajat dua yang saling bertetangga. Fibonacene memiliki sifat yang dikaitkan dengan bilangan Fibonacci. Beberapa sifat - sifat graf dari fibonacene yang telah dikaji diantaranya bilangan saturasi, bilangan independen dan index Wiener. Konsep dimensi partisi graf terhubung diperkenalkan oleh Chartrand dkk [12] pada tahun 1998 yang merupakan perluasan dari konsep dimensi metrik. Dimensi partisi dari graf (G), dinotasikan dengan pd(G), adalah kardinalitas minimum suatu partisi dari himpunan titik V (G) sedemikian sehingga setiap titik mempunyai representasi berbeda terhadap partisi tersebut. Representasi suatu titik dinyatakan oleh jarak titik tersebut terhadap kelas - kelas partisi. Selanjutnya, konsep bilangan kromatik-lokasi diperkenalkan juga oleh Chartrand [10] pada tahun 2002, sebagai perpaduan dari dua konsep yaitu konsep pewarnaan graf dan dimensi partisi. Bilangan kromatiklokasi dari graf G, dinotasikan sebagai L(G), memiliki definisi yang hampir sama dengan dimensi partisi hanya saja pada bilangan kromatik-lokasi setiap dua titik yang bertetangga di G tidak berada pada partisi yang sama. Penentuan bilangan kromatik-lokasi dan dimensi partisi dari sebarang graf merupakan masalah NP-hard. Hal ini berarti tidak ada algoritma yanng efisien dalam menentukan bilangan kromatik-lokasi dan dimensi partisi dari sebarang graf. Bilangan kromatik-lokasi dan dimensi partisi baru dapat ditentukan untuk kelas - kelas graf tertentu. Beberapa kelas graf yang telah diketahui bilangan kromatiklokasinya yaitu pada [10, 11, 3, 27, 28, 4, 18]. Sedangkan beberapa kelas graf yang telah diketahui dimensi partisinya yaitu pada [13, 33, 32, 1, 23, 22]. i Dalam tesis ini akan membahas tentang dimensi partisi dan bilangan kromatiklokasi dari sembarang graf fibonacene.