DIMENSI PARTISI PADA GRAF

Abstract

Diberikan sebuah graf terhubung . Simpul  dikelompokkan ke dalam -partisi yaitu  dengan . Representasi dari  terhadap  yaitu    dengan  dan  merupakan simpul di . Jika representasi yang dihasilkan memiliki vektor koordinat yang berbeda, maka  merupakan partisi pembeda dari graf . Apabila  merupakan nilai minimum dari banyaknya partisi di , maka    merupakan dimensi partisi dari graf , dinotasikan dengan   . Pada penelitian ini dibahas cara menentukan formula dimensi partisi pada graf sisir, graf garis dan graf kuadrat dari graf sisir. Graf sisir adalah graf yang diperoleh dari hasil operasi korona antara graf lintasan  dengan graf lengkap . Graf sisir  memiliki  simpul dan  sisi. Graf garis dari graf sisir  adalah graf yang memiliki jumlah simpul sama dengan jumlah sisi dari graf . Simpul pada graf garis tersebut akan bertetangga jika dan hanya jika sisi-sisi yang bersesuaian saling terhubung pada graf . Graf kuadrat dari graf sisir  yaitu sebuah graf yang memiliki jumlah simpul yang sama dengan simpul pada graf , dengan menambahkan sisi pada dua simpul yang berjarak dua. Hasil dari penelitian ini diperoleh dimensi partisi dari graf sisir yaitu 2, untuk  dan , untuk . Dimensi partisi pada graf garis dari graf sisir yaitu , untuk  dan , untuk  serta dimensi partisi pada graf kuadrat dari graf sisir yaitu , untuk  dan , , untuk . 

Kata Kunci: Partisi pembeda, graf sisir, graf garis, graf kuadrat.