Vol. 20, No. 1, September 2023, pp. 65- 74 DOI: 10.20956/j.v20i1.26808

## The Partition Dimension of The Edge Amalgamation in Cycle Graph

## Dimensi Partisi Hasil Amalgamasi-Sisi pada Graf Siklus
Ananda Dwi Nabila 1* , Hasmawati 2* , Muh. Nur 3*
* Program Studi Matematika, FMIPA-Universitas Hasanuddin
Email : anandadwinabilaa@gmail.com 1 , hasmaba97@gmail.com 2 , muhammadnur@unhas.ac.id 3

## Abstract
The graph is a pair of sets where is a finite set whose elements are called vertices, and is the set of pairs of members of .  which is called the edge. Let be  a  simple  graph  where .  The  distance  between  points and is denoted  by is  the  length  of  the  shortest  path  between and .  Given
and  there  is  a  vertex on  the  connected  graph ,  then  the  distance  between and is denoted . If ∏ is -partition of , then the representation of with  respect  to  is -ordered  pairs, ∏ .  If  the - ordered  pairs ∏ for are  all  different,  then  the  partition  is  called  a
dimension  partition.  The  minimal -number  which  is  the -differentiating  partition  of
is  called  the  partition  dimension  of and  is  denoted  by
.  In  this  study,  the partition  dimensions  of  the  sided  amalgamation  result  will  be  determined  on  an  even- order cycle graph. In determining the dimensions of the partition, characterization of the partition dimensions is used in the path graph, the lemma about the distinguishing set and the equivalence point, especially in the even-order cycle graph. The results of this study are ( ) for , ( ) for
and where
Keywords: Graph  theory,  edge  amalgamation,  partition  dimension,  even  order cycle graph, discrimination partition, equivalent point.

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI
Ananda Dwi Nabila, Hasmawati, Muh. Nur

## Abstrak
Graf adalah  pasangan  himpunan (          ) dengan adalah  himpunan
berhingga  yang  anggota-anggotanya  disebut  titik (vertex) ,  dan adalah  himpunan dari  pasangan  anggota-anggota yang  disebut  sisi (edge) .  Misalkan adalah  graf sederhana  dengan Jarak  antara  titik dan merupakan  lintasan  terpendek antara  titik dan yang  dinotasikan  dengan .  Diberikan sehingga jarak antara titik dan dinotasikan dengan Jika ∏ adalah - partisi dari maka representasi titik terhadap ∏ adalah ∏    ( ) Jika -pasangan  berurutan ∏ untuk semuanya  berbeda,  maka  partisi ∏ disebut  sebagai  partisi  pembeda.  Bilangan minimal yang merupakan partisi pembeda dari disebut dimensi partisi dari dan  dinotasikan  dengan Pada  penelitian  ini  akan  ditentukan  dimensi  partisi  dari
graf hasil amalgamasisi-sisi pada graf siklus orde genap. Dalam penentuan dimensi partisi tersebut digunakan karakterisasi dimensi partisi pada graf path, lemma tentang himpunan pembeda dan titik setara khususnya pada graf siklus orde genap. Hasil dari penelitian ini adalah ( ) untuk , ( ) untuk dan dengan
Kata Kunci: Teori graf, amalgamasi sisi, dimensi partisi, graf siklus orde genap, partisi pembeda, titik setara.

## 1. PENDAHULUAN
Graf adalah  pasangan  himpunan (          ) ,  dengan adalah  himpunan berhingga  yang  anggota-anggotanya  disebut  titik,  dan adalah  himpunan  dari  pasangan anggota-anggota yang  disebut  sisi.  Salah  satu  konsep  teori  graf  yang  menarik  adalah dimensi partisi.
Konsep  partisi  dan  representasi  digunakan  oleh seorang  kimiawan  pada  tahun  1993.  [6] Konsepnya yaitu senyawa kimia direpresentasikan dalam bentuk graf dimana atom menyatakan titik-titik  dari  graf  dan  ikatan  valensi  antara  dua  atom  menyatakan  sisi  dari  graf  tersebut  lalu menentukan  klasifikasi  senyawa  kimia  berdasarkan  konsep  partisi.  Selanjutnya,  pada  tahun 2000    dimensi  partisi  dari  sebuah  graf pertama  kali  dikenalkan  oleh  Chartrand,  Salehi  dan Zhang.  [1]  Mereka  mengelompokkan  semua  titik  di ke  dalam  sejumlah  kelas  partisi  dan menentukan  jarak  setiap  titik  terhadap  setiap  kelas  partisi  tersebut.  Selanjutnya,  mereka membuktikan  dimensi  partisi  dari  graf yang  dinotasikan  dengan bahwa jika dan hanya jika merupakan graf lengkap dan jika dan hanya jika merupakan graf lintasan.
Selain  itu,  terdapat  beberapa  hasil  tentang  dimensi  partisi  pada  suatu  graf  yang  telah diperoleh  diantaranya  yaitu  pada  skripsi  RA.  Novita  Indriyani  [5]  yang  berjudul  “Dimensi Metrik dan Dimensi Partisi pada Graf Amalgamasi-Sisi Siklus Gasal”. Pada penelitian tersebut objek  penelitiannya  adalah  amalgamasi-sisi  siklus.  Pada  tahun  2018,  terdapat  penelitian  yang dilakukan  oleh  Gilang  Arya  Riza  [6]  mengenai  dimensi  partisi  dari  graf  persahabatan.

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI
Selanjutnya,  pada  2019  juga  terdapat  penelitian  yang  dilakukan  oleh  Faisal,  dkk.,  mengenai dimensi  partisi  graf  hasil  operasi  comb    graf  lingkaran  dan  graf  lintasan  [2],  dan  pada  tahun 2022  Hasmawati  dkk  meneliti  mengenai  dimensi  partisi  graf  hasil  amalgamasi  siklus  dimana objek penelitiannya adalah amalgamasi-titik pada graf siklus [4]. Sehingga, Pada jurnal ini akan dibahas  penentuan  dimensi  partisi  hasil  amalgamasi  sisi  pada  graf  siklus dengan . Hasil dalam penelitian ini, ditulis dalam bentuk Lemma dan Teorema.

## 2. TINJAUAN PUSTAKA
Graf adalah  pasangan  himpunan (          ) ,  dengan adalah  himpunan berhingga  yang  anggota-anggotanya  disebut  titik (vertex) ,  dan adalah  himpunan  dari pasangan anggota-anggota yang disebut sisi (edge) . Misalkan adalah  suatu  graf.  Titik dan  sisi Jika
maka dikatakan bahwa titik bertetangga ( adjacent ) dengan titik dan sisi terkait ( incident ) dengan titik begitu pula untuk titik .[3]
Definisi 2.1. Misalkan adalah graf sederhana dimana Jarak antara titik dan dinotasikan dengan adalah

## {
Misalkan { |                  } untuk dan merupakan  kumpulan  graf
berhingga  dan  masing-masing memiliki  sisi  tetap yang  disebut  sisi  pusat. Amalgamasi adalah  graf  yang  dibentuk  dengan  mengambil  semua dan menyatukan  sisi  pusatnya.  Berikut  merupakan  gambaran  dari  graf yang  akan
diteliti.
𝑘 𝑎𝑑𝑎𝑙𝑎ℎ 𝑝𝑎𝑛𝑗𝑎𝑛𝑔 𝑙𝑖𝑛𝑡𝑎𝑠𝑎𝑛 𝑡𝑒𝑟𝑝𝑒𝑛𝑑𝑒𝑘 𝑎𝑛𝑡𝑎𝑟𝑎 𝑢 𝑑𝑎𝑛 𝑣 𝑢   𝑣
𝑗𝑖𝑘𝑎 𝑡𝑖𝑑𝑎𝑘 𝑎𝑑𝑎 𝑙𝑖𝑛𝑡𝑎𝑠𝑎𝑛 𝑎𝑛𝑡𝑎𝑟𝑎 𝑢 𝑑𝑎𝑛 𝑣
𝑝 𝑝 𝑥 𝑥 𝑥 𝑥 𝑥 𝑘 𝑥 𝑘 𝑥 𝑥

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI Ananda Dwi Nabila, Hasmawati, Muh. Nur
Himpunan titik ( )     { } { | dan himpunan sisi ( )   { } .
Definisi 2.2. Diberikan dan terdapat titik pada graf terhubung maka jarak antara dan dinotasikan didefinisikan  sebagai Jika ∏ adalah -partisi  dari maka  representasi terhadap ∏ adalah - pasangan  berurutan, ∏    ( ) Jika -pasangan  berurutan ∏ untuk semuanya  berbeda,  maka  partisi ∏ disebut  sebagai  partisi  pembeda.
Bilangan minimal  yang  merupakan partisi  pembeda  dari disebut  dimensi  partisi dari dan dinotasikan dengan
[1]
Teorema 2.1. Diberikan graf sederhana dan terhubung dengan orde ; maka,
(i) , jika dan hanya jika merupakan graf lintasan, (ii) , jika dan hanya jika merupakan graf lengkap. [8]
Teorema 2.2. Diberikan graf yang bukan merupakan graf lintasan atau graf lengkap dengan orde
maka
. [7]
Definisi  2.3. Diberikan  graf adalah  graf  terhubung  dan Titik dan disebut titik setara dalam graf yang dinotasikan apabila memenuhi salah satu sifat berikut [4] :
1. untuk setiap
2. Terdapat  titik sedemikian  sehingga
/{u,v}.
Lemma 2.1. Diberikan graf terhubung dan
. Jika dan , maka .
Teorema  2.3. Diberikan graf  terhubung  dengan  himpunan  partisi ∏ dari Jika ∏ merupakan partisi pembeda graf dan titik dan merupakan titik-titik yang setara dalam maka dan atau tetangga dan tetangga berada pada kelas partisi yang berbeda di ∏
Definisi  2.4. Diberikan adalah  graf  terhubung  dan .  Titik dan disebut  titik- titik yang setingkat dalam graf apabila memenuhi kedua sifat berikut:
1.
2. Jika , terdapat sehingga dan

## 3. HASIL UTAMA

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI Ananda Dwi Nabila, Hasmawati, Muh. Nur
Hasil utama dalam penelitian ini adalah perumuman dari hasil penentuan dimensi partisi yang akan disajikan dalam bentuk Lemma dan Teorema.
Lemma  3.1. Diberikan  graf dengan memiliki  himpunan  titik (    ( )) { | sehingga  didapatkan  masing-masing
titik , dengan 1
merupakan titik-titik yang setara.

## Bukti.
Berdasarkan Definisi 2.3, diperoleh titik-titik yang setara adalah sebagai berikut:
1. adalah  titik-titik  yang  setara  karena  terdapat  titik sedemikian sehingga ( ) ( ) ( ) ( ) { } . 2. adalah  titik-titik  yang  setara  karena  terdapat  titik sedemikian sehingga ( ) ( ) ( ) ( ) { } . Akibat  3.1. Diberikan  graf dengan  himpunan  titik ( ) { } { | dan himpunan sisi ( )   { } .  Jika merupakan  partisi pembeda untuk , maka titik atau harus berada pada kelas partisi yang berbeda.
Lemma  3.2. Diberikan  graf dengan memiliki  himpunan  titik (    ( )) { | , maka :
a. titik dengan 1 merupakan titik yang setingkat.
b. titik dan merupakan titik yang setingkat.
Bukti.
Berdasarkan Definisi 2.4, diperoleh titik-titik yang setingkat adalah sebagai berikut : 1. adalah  titik-titik  yang  setingkat  karena ( )
( )          ( )      ( ) =  2  dan  banyaknya  titik  yang berjarak  satu  dengan adalah ,  banyaknya  titik  yang berjarak dua dengan adalah , banyaknya titik yang berjarak tiga dengan adalah . 2. adalah titik-titik yang setingkat karena dan banyaknya

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI Ananda Dwi Nabila, Hasmawati, Muh. Nur
titik  yang  berjarak  satu  dengan
adalah ,  banyaknya  titik  yang  berjarak  dua dengan adalah .
Proposisi 3.1. ( ) .
Bukti.
Berikut  merupakan  gambaran  dari  graf  amalgamasi  sisi  siklus sebanyak  empat  yang dinotasikan dengan . Misalkan ∏ dengan { } , { } , { } , dan { } . Representasi titik-titik pada terhadap ∏ adalah sebagai berikut : ∏ ∏ , ∏ ∏ , ∏ ∏ , ∏ , ∏ , ∏ ∏ .
Dapat  dilihat  bahwa  setiap  titik  yang  berada  pada  kelas  partisi  yang  sama  memiliki representasi berbeda terhadap ∏ maka ∏ adalah partisi pembeda. Oleh karena itu, batas atas dari dimensi partisi adalah ( ) .
Selanjutnya  akan  ditentukan  batas  bawah  dari  dimensi  partisi
,  dengan
mengambil partisi pembeda ∏ kardinalitas sama dengan maka diperoleh :
1. Apabila dan berada pada kelas partisi yang sama maka ∏ ∏ atau ∏ ∏ atau  terdapat  titik-titik  setingkat  berada  pada  kelas partisi yang sama dan memiliki representasi yang sama atau terdapat titik-titik setara
𝑝 𝑥 𝑥 𝑥 𝑥 𝑝 𝑥 𝑥 Gambar 3.1. 𝐴𝑚𝑎𝑙 𝐶 𝑒

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI
Ananda Dwi Nabila, Hasmawati, Muh. Nur
berada  pada  kelas  partisi  yang  sama  dan  tetangganya  juga  berada  pada  kelas  partisi yang sama.
2. Apabila dan berada  pada  kelas  partisi  yang  berbeda  maka  terdapat  titik-titik setingkat  berada  pada  kelas  partisi  yang  sama  dan  memiliki  representasi  yang  sama atau  terdapat  titik-titik  setara  berada  pada  kelas  partisi  yang  sama  dan  tetangganya juga berada pada kelas partisi yang sama.
Hal tersebut bertentangan dengan Akibat 3.1 , sehingga batas bawah dari dimensi partisi adalah ( ) . Jadi, ( )
Lemma 3.3. Jika
maka ( )
Bukti .
Semakin besar nilai maka semakin banyak titik-titik yang setara dan titik-titik yang setingkat pada Pada telah  diperoleh ( ) sehingga jika maka ( ) Teorema 3.1. {
Bukti .
Graf memiliki titik (    ( )) { | dengan sisi pusat . Berdasarkan Teorema 3.1, pembuktian akan dibagi ke dalam tiga kasus yaitu untuk dan Untuk , telah dibuktikan dan diperoleh Untuk , akan dibuktikan Pada batas atas dari dimensi  partisinya  pilih ∏ dengan { } , { } , { } untuk , dan { } .
𝑚 𝑘    𝑚 dan 𝑘    𝑚    ;

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI
Ananda Dwi Nabila, Hasmawati, Muh. Nur
Representasi setiap titik terhadap ∏ adalah
∏    ( ⏟ ) ,
∏    ( ⏟ ) , ∏    ( ⏟ ) ∏    ( ⏟ ) , ∏    ( ⏟ ) ∏    ( ⏟ ) ,
∏    ( ⏟ ⏟ ) ;
, ∏    ( ⏟ ( ) ⏟ , ; ,
∏    ( ⏟ ⏟ + ;
, ∏    ( ⏟
( ) ⏟ (  ( )* , ; , ∏    ( ⏟ ) ,

## ∏    ( ⏟ ) .
Dapat  dilihat  bahwa  setiap  titik  yang  berada  pada  kelas  partisi  yang  sama  memiliki representasi berbeda terhadap ∏ maka ∏ adalah partisi pembeda. Oleh

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI
Ananda Dwi Nabila, Hasmawati, Muh. Nur
karena  itu,  batas  atas  dari  dimensi  partisi
dengan adalah
( ) .
Selanjutnya  akan  ditentukan  batas  bawah  dari  dimensi  partisi
,
mengambil partisi pembeda ∏ dengan kardinalitas lebih kecil dari diperoleh :
1. Terdapat  titik-titik  yang  setara  ( merujuk  ke  Lemma  3.1 )  pada yaitu dengan
dan  tetangga  dari berada  di ,  tetangga  dari berada  di tetangga  dari berada  di
akibatnya  tidak  terdapat  titik  setara  pada yang
tetangganya  berada  pada  kelas  partisi  yang  sama.  Selanjutnya,  apabila  titik-titik  pada atau atau atau didistribusikan  sembarang  maka  terdapat  dua  titik  berada pada  kelas  partisi  yang  sama  dan  dua  titik  tersebut  merupakan  tetanggga  dari  dua  titik setara  yaitu atau atau atau yang  berada  pada sehingga  kedua  titik setara  itu  memiliki  representasi  yang  sama  terhadap  himpunan  partisi.  Berdasarkan Akibat  3.1 ,  hal  tersebut  tidak  boleh  terjadi.  Akibatnya  himpunan  partisi  yang  memuat 2+m kelas partisi bukan merupakan partisi pembeda.
2. Apabila titik-titik pada didistribusikan sembarang maka terdapat dua kasus berikut.
Kasus  1. berada  di  kelas  yang  sama  dengan sehingga  terdapat  beberapa subkasus berikut.
 Setiap  kelas  partisi  terdapat atau atau atau sehingga mengakibatkan ∏ ∏ .
 Terdapat dua atau lebih titik setara berada pada kelas yang sama dan tetangga dari titik setara tersebut juga berada pada kelas yang sama.
Kasus  2. berada  di  kelas  yang  berbeda  dengan sehingga  terdapat  beberapa subkasus berikut.
 Terdapat  titik  setingkat  yang  berada  pada  kelas  partisi  yang  sama  namun tetangga dari titik setingkat tersebut juga berada pada kelas partisi yang sama.
 Terdapat  dua  titik  setara  dan  tetangga  dari  dua  titik  setara  tersebut  juga berada  pada  kelas  partisi  yang  sama.  Akibatnya    dua  titik  setara  tersebut memiliki representasi yang sama.
Dapat  dilihat  bahwa  untuk  setiap  kelas  partisi  selalu  terdapat  representasi  titik  yang sama  terhadap ∏ .  Sehingga,  partisi  pembeda ∏ kardinalitas  lebih  kecil  dari bukan
himpunan pembeda dari dengan Oleh karena itu, batas bawah dari dimensi partisi dengan adalah ( ) .

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI Ananda Dwi Nabila, Hasmawati, Muh. Nur
Jadi, untuk diperoleh ( ) .
Untuk ,  akan  dibuktikan  dengan  cara  yang  sama  pada  saat  menunjukkan untuk diperoleh Sehingga diperoleh, jika maka . Selanjutnya,  karena ( ) untuk , untuk dan maka Teorema 3.1 telah terbukti benar.

## 4. KESIMPULAN
Dari  hasil  yang  diperoleh,  didapatkan  kesimpulan  bahwa  dimensi  partisi  dari  graf terbagi  menjadi  dua  yaitu ( ) untuk , ( ) untuk dan .

## DAFTAR PUSTAKA
[1]  Chartrand,  G.,  Salehi,  E.,  &  Zhang,  P.,  2000.  The  Partition  Dimension  of  a  Graph. Aequationes Mathematica , 59, 45-54.
[2]  Faisal., Mardiana, N., & Rosiyanti, H., 2019. Dimensi Partisi Graf Hasil Amalgamasi Comb Graf Lingkaran dan Graf Lintasan. Jurnal Pendidikan Matematika dan Matematika , Vol. 5, No 2, 163-174.
[3]  Hasmawati., 2015. Bahan Ajar Teori Graf. Universitas Hasanuddin, Makassar.
[4]  Hasmawati., Hinding, N., Nurwahyu, B., Daming, A. S., & Amir, A. K., 2022. The Partition Dimension of The Vertex Amalgamation of Some Cycles. Heliyon , Vol. 8, Issue 6.
[5]  Indriyani,  RA.  N.,  2013.  Dimensi  Metrik  dan  Dimensi  Partisi  pada  Graf  Amalgamasi  Sisi Siklus Gasal. Universitas Airlangga, Surabaya.
[6]  Liza, G. A., 2018. Dimensi Partisi dari Graf Persahabatan. Jurnal Matematika UNAND , Vol. 7, No. 3, 54-58.
[7] Monica, Mohan. C., Santhakumar, S., 2019. Partition Dimension of Rooted Product Graphs. Elseiver , Vol. 262, No. 12, 138-147.
[8] Wei, C., Nadeem, M. F., Siddiqui, H. M. A., Azeem, M., Liu, J., & Khalil, A., 2021. On Partition Dimension of Some Cycle-Related Graphs. Hindawi, Vol. 2021, No. 4, 1-8.