Vol. 17, No. 3,  472-483,  May, 2021

## DOI: 10.20956/j.v17i3.13596
*Department of Mathematics, Hasanuddin University, Indonesia Email : hasmawati@unhas.ac.id 1 ;budinurwahyu@gmail.com 2 ; ahmadsyukurd@gmail.com 3 , amirkamalamir@yahoo.com 4

## Partition Dimention of Dutch Windmill Graph

## Dimensi Partisi Graf Kincir Angin Belanda
Hasmawati 1 * , Budi Nurwahyu 2* , Ahmad Syukur Daming 3 * ,
Amir Kamal Amir 4*

## Abstract
Let be a connected graph G and -partition { } of end . The coordinat to is | .  If  every  two  vertices  is  distinct applies |        | ,  then is  a  called partition  of .  The  minimum  k  for  which  k- resolving  partition  of is  the  partition  dimension and  denoted  with .  In  this  paper,  we
investigates the partition dimension for a large Dutch  windmill graph
for and . We  show that if [ ] for some , for any .
Keywords: Partition Dimention, Amalgamation, Cycle Graph
Abstrak
Misalkan  terdapat  sebuah  graf  terhubung dan buah  partisi { } dari dan
. Koordinat terhadap didefinisikan sebagai | . Jika
untuk setiap dua titik berbeda
berlaku |        | , maka disebut -partisi pembeda dari . Nilai  minimum agar  terdapat -partisi  pembeda  dari adalah  dimensi  partisi dari atau  sering  dinotasikan  dengan
.  Dalam  makalah  ini  amalgamasi  graf  siklus disebut graf kincir angin Belanda dengan notasi
dan dimensi partisinya dinotasikan Pada  penelitian  ini  telah  ditunjukkan  bahwa  untuk  suatu , untuk suatu bilangan positif dan * + .
Kata kunci: Dimensi Partisi, Amalgamasi, Graf Siklus .

## 1. Pendahuluan
Graf  adalah  pasangan  himpunan  terurut
,  dan  ditulis  dengan  notasi
,
dengan adalah himpunan tidak kosong yang anggotanya disebut titik dan adalah himpunan pasangan–pasangan tidak terurut dari anggota yang disebut sisi. Salah satu kajian dalam teori graf  yang  mendapat  perhatian  dari  beberapa  peneliti  adalah  dimensi  partisi  ( partition dimension ).  Dimensi  partisi  pertama  kali  diperkenalkan  oleh  Chartrand  dkk  [4].  Mereka mengelompokkan semua titik di ke dalam sejumlah kelas partisi dan menentukan jarak setiap titik terhadap setiap kelas partisi tersebut.

## Jurnal Matematika, Statistika & Komputasi
Hasmawati, Budi Nurwahyu, Ahmad Syukur Daming , Amir Kamal Amir
Terdapat  beberapa  hasil  tentang  dimensi  partisi  suatu  graf    yang  telah  diperoleh diantaranya  [5]  membuktikan  bahwa  sebuah  graf mempunyai jika  dan hanya  jika adalah  graf  lintasan dan  menunjukkan  bahwa  graf mempunyai jika  dan  hanya  jika adalah  graf  lengkap .  Dalam  makalah  [10], disajikan  batas  atas  dan  bawah  dimensi  partisi  untuk  graf  pohon.  Sedangkan  makalah [1],  menyajikan  dimensi  partisi  graf  amalgamasi  bintang.  Dimensi  partisi  graf amalgamasi bintang dan lintasan disajikan dalam makalah [2], sedangkan makalah [6], membahas  dimensi  partisi  untuk  graf  persahabatan.  Dalam  makalah  ini  dibahas penentuan  dimensi  partisi  untuk  graf  amalgamasi  siklus.  Beberapa  metode  yang disajikan  pada  makalah  [2]  dan  [5]  akan  dikembangkan  untuk  digunakan  dalam penentuan  dimensi  partisi  graf  amalgamasi  siklus.  Hasil  yang  diperoleh  dalam penelitian  ini,  ditulis  dalam  bentuk  Lema  dan  proposisi,  dan  di  akhir  buktinya  diberi tanda .

## 2. Tinjauan Pustaka
Graf yaitu    pasangan himpunan
dimana adalah  himpunan berhingga  tak  kosong  yang  anggota-anggotanya  disebut  titik,  dan adalah  sebuah himpunan (mungkin kosong) dari pasangan pasangan titik yang disebut sisi.
Graf disebut graf terhubung ( connected ), jika untuk setiap dua titik yang berbeda di terdapat  suatu  lintasan  dari ke [3].  Panjang  suatu  lintasan  adalah  banyaknya sisi yang ada pada lintasan tersebut.
Misal adalah  graf sederhana dan .  Jarak  antara  titik dan dinotasikan  dengan dan  lintasan  berorde dinotasikan  dengan dengan .  Jika adalah  suatu  graf  lintasan berorde dan ,  maka  graf siklus adalah  graf  dengan  himpunan  titik dan  himpunan  sisi
{ } .  Graf  siklus memiliki titik  dan sisi  dengan  setiap titiknya berderajat dua.
Misalkan { |    {            }} untuk dan ,  merupakan  kumpulan  graf
berhingga  dan  masing–masing memiliki titik  tetap yang  disebut  terminal. Amalgamasi
adalah graf yang dibentuk dengan mengambil semua dan menyatukan  terminalnya  [9].  Graf  yang  akan  di  diteliti  dalam  penelitian  ini  adalah dengan untuk  setiap , dan
. Untuk penyederhanaan  penulisan,  dalam  penelitian  ini  sisi {    } hanya  ditulis dan ( ) hanya ditulis
.

## Jurnal Matematika, Statistika & Komputasi
Hasmawati, Budi Nurwahyu, Ahmad Syukur Daming , Amir Kamal Amir
Gambar 1. Graf Hasil Amalgamasi Siklus (
Himpunan  titik { |                       } dan  himpunan  sisi { |                        } . Misalkan  terdapat sebuah  graf  terhubung dengan adalah  himpunan  titik-titiknya,
dan
, jarak antara dengan yang dinotasikan dan didefinisikan sebagai
{       |     } Misalkan terdapat sebuah graf terhubung dan koleksi himpunan {
} ,  dengan adalah  partisi  dari Himpunan
{ } disebut himpunan  partisi dan disebut kelas  partisi. Misalkan .  Representasi  (koordinat) terhadap didefinisikan  sebagai | (
) .  Himpunan  partisi { } dikatakan - partisi  pembeda ( resolving  partition )  jika -vektor | untuk  setiap adalah  berbeda.  Nilai  minimum agar  terdapat -partisi  pembeda  dari adalah
dimensi partisi dari . Dimensi partidsi dari dinotasikan dengan [5]. Definisi dan hasil penelitian dalam [6] yang terkait dengan penelitian ini, disajikan dalam bentuk definisi dan Teorema berturut-turut sebagai berikut:
Definisi  2.1. Diberikan adalah  graf  terhubung  dan .  Titik dan disebut  titik- titik yang setara dalam graf apabila memenuhi salah satu sifat berikut:
a. untuk setiap {    } ,
b. terdapat  titik sehingga untuk  setiap
{    } . Teorema 2.1. Setiap bilangan asli , ,

## 3. Hasil Utama
Hasil utama yang dibahas dalam makalah ini adalah perumuman dari hasil Ahmad Syukur dkk.,[6], yang disajikan pada Proposisi 3.2. Beberapa pernyataan yang cukup membantu dalam membuktikan Proposisi 3.2 disajikan dalam bentuk Lema 3.1 dan Proposisi 3.1.
Lema 3.1. Diberikan G graf terhubung dengan himpunan partisi dari . Misalkan
pula titik dan titik-titik yang setara dalam . Jika merupakan partisi pembeda graf , maka dan atau tetangga dan tetangga berada pada kelas partisi yang berbeda di .
Bukti. Misalkan {
} ,    adalah  partisi  pembeda  graf .  Berarti  setiap {          } , untuk setiap titik dan di graf . Misalkan pula dan adalah titik yang setara pada graf , dan
serta . Misalkan terdapat {          } sehingga dan
,    maka
dan .  Selanjutnya,  ambil  sembarang  titik {          } dan misalkan .  Karena titik dan adalah  titik-titik  yang  setara,  terdapat

## Jurnal Matematika, Statistika & Komputasi
Hasmawati, Budi Nurwahyu, Ahmad Syukur Daming , Amir Kamal Amir
sehingga .  Akibatnya, .  Dengan
demikian, diperoleh | = | , yang berarti { } bukan paritsi pembeda untuk  graf .  Padahal  diketahui { } merupakan  partisi  pembeda. Karenanya,  mestilah  titik dan atau  tetangga dan  tetangga berada  pada  kelas partisi yang berbeda di .
Proposisi  3.1. Diberikan  graf dengan  himpunan  titik { |                       } dan himpuan sisi { |                       } . Maka : a. untuk setiap , titik dan titik untuk dengan
merupakan titik-titik yang  tidak setara .
b. untuk setiap dan dengan ⌊ ⌋ , titik dan adalah titik-titik yang setara.
Bukti .
Labeli titik-titik pada siklus di graf
sebagai berikut:
. Jadi himpunan sisinya adalah { | a. Ambil sembarang , dan sembarang .  Titik dan titik di graf memiliki jarak yang sama terhadap titik . Jadi = ( ) Pilih titik sehingga terdapat lintasan dari ke . Akibatnya ( )    ( ) = ( )    ( ) . Jadi ( ) ( ) . Sekarang perhatikan titik titik , ( ) , sedangkan ( )    ( )    ( )      {        }       { } . Jadi ( ) ( ) Jadi terdapat titik di sebut sehingga ( ) ( ) . Menurut Definisi 2.1, titik dan titik untuk setiap adalah titik yang tidak setara. b. Ambil sembarang , dan sembarang , sebut Titik dan adalah titik pada siklus dengan ( ) dan ( ) . Jadi ( ) = ( ) . Dapat dilihat bahawa dan adalah tetangga dari titik . Sedangkan titik dan adalah tetangga dari titik . Jarak masing-masing titik ke titik tetangganya adalah  sama seperti yang diperlihatkan berikut. ( )    ( )    ( ) ; ( )    ( )    ( ) ; dan ( )    ( )    ( )   (           ) ; ( )    ( )    ( )   (           ) ; Jadi Menurut Definisi 2.1, titik dan titik adalah titik yang setara.

## Jurnal Matematika, Statistika & Komputasi
Hasmawati, Budi Nurwahyu, Ahmad Syukur Daming , Amir Kamal Amir
Akibat  3.1. Diberikan  graf dengan  himpunan  titik { |                       } dan himpuan sisi { |                       } . Jika merupakan
partisi  pembeda  untuk maka titik dan
, dan atau dan , n ,  berada pada kelas partisi yang berbeda.
Bukti. Menurut Proposisi 3.1 , setiap dan dengan ⌊ ⌋ , titik dan adalah titik- titik  yang  setara  dan adalah  tetangga  dari  titik serta dan adalah tetangga dari , menurut Lemma 3.1 titik dan , dan atau dan , n ,  berada pada kelas partisi yang berbeda. Proposisi 3.2: Misalkan dan ,      | - . Jika untuk suatu , maka untuk setiap Bukti : Pilih dengan dan ambil sembarang di Misalkan pula label
himpunan titik dan himpunan sisi graf
berturut-turut { |                       } dan { | } .
Bentuk  himpunan  partisi { } dari  himpunan  titik untuk .  Label titik pada siklus-siklus graf , sebagai berikut: . Dengan menggunakan Proposisi 3.1 dan Akibat 3.1 untuk didefinisikan { }   { ⌊ ⌋ } { ⌊ ⌋ ⌊ ⌋ } { ⌊ ⌋ ⌊ ⌋ } { ⌊ ⌋ ⌊ ⌋ } ... { ⌊ ⌋ ⌊ ⌋ } ;
dengan

## Jurnal Matematika, Statistika & Komputasi
Hasmawati, Budi Nurwahyu, Ahmad Syukur Daming , Amir Kamal Amir
∑ ;
{ ⌊ ⌋ } { ⌊ ⌋ ⌊ ⌋ } { ⌊ ⌋ ⌊ ⌋ } { ⌊ ⌋ ⌊ ⌋ } ... { ⌊ ⌋ ⌊ ⌋ }                 ∑ ; { ⌊ ⌋ } { ⌊ ⌋ } { ⌊ ⌋ ⌊ ⌋ } { ⌊ ⌋ ⌊ ⌋ } ... { ⌊ ⌋ ⌊ ⌋ }                ∑ ; { ⌊ ⌋ ⌊ ⌋
⌊ ⌋ }   { } , dan
{ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ } . untuk dan Sekarang akan diselidiki apakah  representasi titik-titik  c, , for and berlaku ( | )      ( | ) untuk
, |
( | ) dan
( | ) , jika ⌈ ⌉ ,

## Jurnal Matematika, Statistika & Komputasi
Hasmawati, Budi Nurwahyu, Ahmad Syukur Daming , Amir Kamal Amir
( | )   (⌈ ⌉                             ) , jika ⌈ ⌉           ⌈ ⌉ , ( | )   ( ⌈ ⌉ ) , jika ⌈ ⌉
⌈ ⌉ , ( | ) ,
jika ⌈ ⌉ ,
( | ) , ( | ) dan
( | ) , jika ⌈ ⌉ ,
( | )   (⌈ ⌉                               ) , jika ⌈ ⌉           ⌈ ⌉ ,
( | )   (                   ⌈ ⌉                   ) , jika ⌈ ⌉           ⌈ ⌉ ,
( | ) ,
jika ⌈ ⌉ ,
( | )
( | )
( | ) , jika ⌈ ⌉ ,
( | )   (   ⌈ ⌉                     ) , jika ⌈ ⌉           ⌈ ⌉ ,

## Jurnal Matematika, Statistika & Komputasi
Hasmawati, Budi Nurwahyu, Ahmad Syukur Daming , Amir Kamal Amir
( | )   (              ⌈ ⌉                          ) , jika ⌈ ⌉           ⌈ ⌉ ,
( | ) , jika ⌈ ⌉ ,
( | ) ,
( | )
( | ) , jika ⌈ ⌉ ,
( | )   (⌈ ⌉                                      ) , jika ⌈ ⌉           ⌈ ⌉ ,
( | )   (                                 ⌈ ⌉               ) , jika ⌈ ⌉           ⌈ ⌉ ,
( | ) , jika ⌈ ⌉ , ( | ) ( | ) , ( | ) , jika ⌈ ⌉ ,
( | )   (⌈ ⌉                               ) , jika ⌈ ⌉           ⌈ ⌉ ,
( | )   (                                        ⌈ ⌉    ) , jika ⌈ ⌉           ⌈ ⌉ ,

## Jurnal Matematika, Statistika & Komputasi
Hasmawati, Budi Nurwahyu, Ahmad Syukur Daming , Amir Kamal Amir
( | ) , jika ⌈ ⌉ ,
( | ) , untuk .
( | )
( | ) , jika ⌈ ⌉ ,
( | )   (⌈ ⌉                               ) , jika ⌈ ⌉           ⌈ ⌉ ,
( | )   (                                    ⌈ ⌉    ) , jika ⌈ ⌉           ⌈ ⌉ ,
( | ) , jika ⌈ ⌉ ,
( | ) ( | ) ( | ) , jika ⌈ ⌉ ,
( | )   (⌈ ⌉                                ) , jika ⌈ ⌉           ⌈ ⌉ ,
( | )   (                                    ⌈ ⌉    ) , jika ⌈ ⌉           ⌈ ⌉ ,
( | ) , jika ⌈ ⌉
,

## Jurnal Matematika, Statistika & Komputasi
Hasmawati, Budi Nurwahyu, Ahmad Syukur Daming , Amir Kamal Amir
( | )
Dapat dilihat bahwa representasi titik
terhadap untuk setiap semuanya berbeda. Dengan kata lain, untuk setiap | | . Jadi adalah partisi pembeda graf
sehingga diperoleh . ………………….…(a) Selanjutnya,  menentukan  batas  bawah  dari  dimensi  partisi .  Ambil
sembarang himpunan partisi dari graf sebut dengan | | . Pilih
dan distribusi anggota-anggota ke . Tanpa mengurangi perumuman, untuk dimisalkan = { ⌊ ⌋ } { }   { ⌊ ⌋ } { ⌊ ⌋ ⌊ ⌋ } { ⌊ ⌋ ⌊ ⌋ } { ⌊ ⌋ ⌊ ⌋ } ... { ⌊ ⌋ ⌊ ⌋ } { ⌊ ⌋ } ; dengan ∑ ; { ⌊ ⌋ }   { ⌊ ⌋ } { ⌊ ⌋ ⌊ ⌋ } { ⌊ ⌋ ⌊ ⌋ } { ⌊ ⌋ ⌊ ⌋ } ... { ⌊ ⌋ ⌊ ⌋ } { ⌊ ⌋ }                 ∑ ;

## Jurnal Matematika, Statistika & Komputasi
Hasmawati, Budi Nurwahyu, Ahmad Syukur Daming , Amir Kamal Amir
{ ⌊ ⌋ }   { ⌊ ⌋ } { ⌊ ⌋ } { ⌊ ⌋ ⌊ ⌋ } { ⌊ ⌋ ⌊ ⌋ } ... { ⌊ ⌋ ⌊ ⌋ } { ⌊ ⌋ }                ∑ ;
{ ⌊ ⌋ } { ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ }   { }
{ ⌊ ⌋ } dengan untuk . Perhatikan  titik-titik dan  titik untuk ⌈ ⌉ , berada  pada  kelas  partisi yang  sama  yakni  pada  partisi Tetangga dan
juga  berada  pada  kelas
partisi  yang  sama.  Menurut Proposisi  3.1 titik-titik dan  titik adalah  titik setara, sehingga menurut Lema 3.1,
{ } bukan partisi pembeda untuk graf
. Akibatnya . …………………………………… (b) Berdasarkan Persamaan (a) dan (b) diperoleh .

## 4. Kesimpulan
Berdasarkan Teorema 2.1 dan Proposisi 3.2 dapat disimpulkan bahwa untuk suatu
, untuk suatu
dan .

## 5. Saran
Penelitian perlu dilanjutkan yakni menyelidiki apakah untuk setiap dengan dan .

## Jurnal Matematika, Statistika & Komputasi
Hasmawati, Budi Nurwahyu, Ahmad Syukur Daming , Amir Kamal Amir

## Daftar Pustaka
[1] Asmiati,  2012.  Partition  Dimension  of  Amalgamation  of  Stars. Bulletin  of  Mathematics . 02(04): 161-167.
[2] Asmiati,  2016.  Dimensi  Partisi Graf  Amalgamasi  Bintang  yang  Dihubungkan  Suatu Lintasan. Jurnal  Matematika,  Fakultas  Matematika  dan  Ilmu  Pengetahuan  Alam Universitas Lampung . 19(3): 93-95.
[3] Chartrand,  G.,  dan  Oellermann,  O.  R.  1993. Applied  and  Algorithmic  graph  Theory . McGraw–Hill, Inc, New York–St. Louis–San Francisco.
[4] Chartrand,  G.,  Salehi,  E.,  dan  Zang,  P.  1998.  On  The  Partition  Dimension  of  Graph. Congressus Numerantium . Vol. 130: 157-168.
[5] Chartrand,  G.,  Salehi,  E.,  dan  Zang,  P.  2000.  The  Partition  Dimension  of  Graph. Aequationes Mathematicae . 59: 45-54.
[6] Daming, A., S., Hasmawati, Haryanto, L., Nurwahyu B., 2020. Dimensi Partisi Graf Hasil Amalgamasi Siklus, JMSK , VOL.6, No.2, 199-207
[7] Darmaji,  2011. Dimensi  Partisi  Graf  Multipartit  dan  Graf  Hasil  Korona  Dua  Graf Terhubung. Disertasi . Bandung: Institut Teknologi Bandung, Indonesia.
[8] Diestel R. 2005. Graph Theory , Third Edition. Springer-Verlag Heidelberg. New York.
[9] Fitriani, D., Salman, A. N. M. 2016. Rainbow connection number of amalgamation of some graphs. AKCE International journal of graphs and combinatorics . 13 : 90–99.
[10] Juan,  R.,  Yero,  I.  G.,  dan  Lemanska,  M.  2014.  On  the  Partition  Dimension  of  Trees. Discrete Applied Mathematics . 166: 204-209.