Perpustakaan Digital ITB

Misalkan G = (V:E) adalah suatu graf dengan V merupakan himpunan titik yang berhingga, dan E merupakan himpunan sisi. Jarak antara dua titik v:w 2 V (G), dinotasikan dengan dG (u: v), adalah panjang lintasan terpendek dari titik u ke titik v di G. Misalkan W = fw1:w2: : : : :wkg adalah subhimpunan dari V (G). Untuk setiap v 2 V (G), representasi titik v terhadap W didefinisikan sebagai k-pasang terurut r (v j W) = (dG (v:w1) : dG (v:w2) : : : : : dG (v:wk)). Himpunan W dikatakan sebagai himpunan pembeda dari G, jika untuk setiap dua titik berbeda x: y 2 V (G) berlaku r (xjW) 6= r (yjW). Basis dari G adalah himpunan pembeda dari G dengan kardinalitas terkecil. Dimensi metrik dari graf G, dinotasikan dengan B (G), didefinisikan sebagai banyak elemen dari suatu basis di G. Salah satu kajian menarik dalam dimensi metrik adalah penentuan dimensi metrik dari suatu graf G hasil operasi graf tertentu, dengan mengaitkan dimensi metrik dari graf G dengan dimensi metrik graf-graf pembentuknya. Operasi graf yang kami tinjau dalam disertasi ini adalah operasi komposisi dari dua buah graf Pada penelitian ini, kami memberikan suatu batas atas dan batas bawah yang ketat bagi beta. Selain itu, kami juga memberikan nilai eksak Beta(G(H)) untuk kasus G adalah graf lintasan Pn atau graf lengkap Kn, dan H adalah graf bintang Sm.