Dimensi Partisi pada Graf Payung

Abstract

Dimensi metrik, dimensi partisi, dan bilangan kromatik-lokasi dari suatu graf merupakan tiga macam konsep dimensi dalam graf yang berkaitan. Untuk memperoleh cara pandang baru terhadap permasalahan penentuan dimensi metrik graf, Chartrand, Salehi, dan Zhang pada tahun 2000 memperkenalkan suatu konsep baru yang selanjutnya dikenal sebagai dimensi partisi graf. Andaikan G(V,E) suatu graf terhubung dengan himpunan titik V dan himpunan sisi E. Diberikan partisi Π dari V(G) dengan k kelas komponen dalam bentuk Π={L_1,L_2,⋯,L_k}. Representasi dari titik t terhadap Π didefinisikan sebagai vektor dengan k komponen dapat ditulis dalam bentuk r(t│Π)=(d(t,L_1 ),d(t,L_2 ),⋯,d(t,L_k )), dimana k merupakan bilangan bulat positif. Untuk suatu graf G terhubung dan suatu subhimpunan L⊂V(G), partisi Π disebut partisi pembeda dari graf G jika semua representasi dari titik t∈V(G) berbeda terhadap Π. Bilangan bulat positif terkecil k adalah dimensi partisi pada graf G yang dinotasikan dengan pd(G). Pada penelitian ini akan ditentukan dimensi partisi pada graf payung U_(m,n) (1) dan U_(m,n) (2). Graf U_(m,n) (1) merupakan suatu graf hasil penggabungan sebuah graf roda W_(1,n) dan lintasan P_n. Graf U_(m,n) (2) merupakan suatu graf hasil penggabungan sebuah graf kipas F_(1,n) dan lintasan P_n.