Perpustakaan Digital ITB

Misalkan G = (V (G),E(G)) adalah graf terhubung dan berhingga. Misalkan himpunan terurut W = {w1,w2, . . . ,wk} merupakan subhimpunan dari V (G). Representasi titik v ? V (G) terhadap W didefinisikan sebagai r(v|W) = (d(v,w1), d(v,w2), . . . , d(v,wk)), dengan d(v,wi) menyatakan jarak v dan wi. Himpunan W dikatakan himpunan pembeda dari G, jika setiap titik dari G mempunyai representasi yang berbeda. Suatu himpunan pembeda dengan kardinalitas minimum disebut basis dari G. Lebih lanjut, banyaknya titik dalam basis G didefinisikan sebagai dimensi metrik dari G yang dinotasikan dengan dim(G). Himpunan pembeda W disebut himpunan pembeda tanpa titik terisolasi, jika subgraf yang diinduksi ?W? tidak mempunyai titik terisolasi. Suatu himpunan pembeda tanpa titik terisolasi dari G dengan kardinalitas minimum disebut himpunan-nr dari G. Kardinalitas dari himpunan-nr disebut bilangan pembeda tanpa titik terisolasi yang dinotasikan dengan nr(G). Graf hasil operasi korona G dengan graf H, dinotasikan dengan G ? H, didefinisikan sebagai graf yang diperoleh dari satu salinan G dan |V (G)| salinan H, sebut H1,H2, . . . ,H|V (G)|, sehingga setiap titik di Hi bertetangga dengan titik ke-i di G. Misalkan H adalah graf terhubung dan o suatu titik di H. Graf hasil operasi sisir titik G dengan H di o, dinotasikan dengan G ?o H, adalah graf yang diperoleh dengan mengambil satu salinan dari G dan sebanyak |V (G)| salinan di H, sebut H1,H2, . . . ,H|V (G)|, dengan cara menempelkan titik o di Hi ke titik i di G. Pada disertasi ini, ditentukan batas atas dan batas bawah yang ketat untuk bilangan pembeda tanpa titik terisolasi graf hasil operasi korona dan operasi sisir titik. Selain itu, ditentukan pula bilangan pembeda tanpa titik terisolasi beberapa kelas graf hasil operasi korona dan operasi sisir titik.