Limits: Journal of Mathematics and Its Applications E-ISSN: 2579-8936 P-ISSN: 1829-605X Vol. 21, No. 1, Maret 2024, 1-12 DOI: http://dx.doi.org/10.12962/limits.v21i1.13502

## Pelabelan Koprima Pada Amalgamasi Graf Lengkap dan Graf Berlian
Hafif Komarullah 1 , Slamin 2 , Kristiana Wijaya 1 *
1 Graph and Algebra Research Group, Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Jember 2 Program Studi Sistem Informasi, Universitas Jember e-mail: kristiana.fmipa@unej.ac.id
Diajukan: 2 Juli 2022, Diperbaiki: 22 Nopember 2023, Diterima: 15 Maret 2024

## Abstrak
Pelabelan koprima pada graf berorder 𝑛𝑛 adalah pemberian label berbeda pada setiap titik pada graf dengan  bilangan 1, 2, … , 𝑘𝑘 ,  untuk suatu 𝑘𝑘 ≥ 𝑛𝑛 , sedemikian sehingga setiap dua titik yang bertetangga mempunyai label yang relatif prima. Jika 𝑘𝑘 = 𝑛𝑛 , pelabelan koprima secara khusus dinamakan pelabelan prima. Setiap graf pasti memenuhi pelabelan koprima. Oleh karena itu, permasalahan pada pelabelan koprima adalah mendapatkan nilai 𝑘𝑘 terkecil, yang disebut bilangan koprima terkecil, yaitu nilai terkecil dari kemungkinan label terbesar yang digunakan sehingga memenuhi aturan pelabelan koprima. Pada paper ini dibahas bilangan koprima terkecil dari graf hasil amalgamasi pada graf lengkap. Selanjutnya dibahas juga bilangan koprima terkecil dari graf berlian dan graf hasil amalgamasi pada graf berlian. Kata Kunci : Pelabelan koprima, bilangan koprima terkecil

## Abstract
A coprime labeling of a graph of order n is a labeling of the vertices in graph with distinct integer 1, 2, … , 𝑘𝑘 , for some 𝑘𝑘 ≥ 𝑛𝑛 , in such a way that the labels of any two adjacent vertices are relatively prime. A graph is prime if the labels used can be taken to be the first n positive integers, namely 𝑘𝑘 = 𝑛𝑛 . If a graph is not prime, the problem is finding the minimum of the largest label of each vertex such that the labels of two adjacent vertices are relatively prime, called a minimum coprime number. In this paper, we discuss a minimum coprime number of amalgamation of complete graphs. Furthermore, we discuss the minimum coprime number of a diamond graph and its amalgamation.
Keywords : A coprime labeling, minimum coprime number

## 1 Pendahuluan
Misalkan 𝐺𝐺 adalah graf dengan 𝑛𝑛 titik. Pelabelan koprima pada graf 𝐺𝐺 didefinisikan sebagai pemetaan 𝑓𝑓 dari himpunan titik 𝐺𝐺 ke himpunan bilangan bulat positif {1, 2, … , 𝑘𝑘 } dengan 𝑘𝑘 ≥ 𝑛𝑛 , sedemikian sehingga label dari setiap  dua  titik yang bertetangga bersifat  relatif prima. Dua bilangan bulat positif 𝑎𝑎 dan 𝑏𝑏 dikatakan relatif prima jika faktor persekutuan terbesarnya satu, yaitu gcd( 𝑎𝑎 , 𝑏𝑏 ) = 1 [1]. Jika 𝑘𝑘 = 𝑛𝑛 maka pelabelan koprima disebut pelabelan prima [2]. Graf yang dapat diberi label dengan aturan prima (koprima) disebut graf prima ( koprima ). Tentu saja setiap graf belum tentu prima, tetapi setiap graf pasti koprima, yaitu dengan menggunakan label 1

## 2
dan ( 𝑛𝑛 − 1) bilangan prima pertama.  Dengan demikian permasalahan pada pelabelan koprima tidak hanya berfokus pada pola pelabelannya, tetapi mendapatkan nilai 𝑘𝑘 > 𝑛𝑛 terkecil sedemikian sehingga syarat koprima terpenuhi. Nilai minimum dari label terbesar 𝑘𝑘 pada pelabelan koprima ini disebut bilangan koprima terkecil , dinotasikan 𝔭𝔭𝔭𝔭 ( 𝐺𝐺 ).
Konsep pelabelan prima bermula dari  Entringer pada tahun 1980 yang menduga bahwa semua graf pohon adalah prima. Selanjutnya Tout, Dabboucy,  dan Howalla pada tahun 1984 memperkenalkan pelabelan prima.  Graf persahabatan, graf bunga, graf bistar merupakan graf prima  [3]. Graf tripartit lengkap juga merupakan graf prima [4]. Dugaan bahwa graf tangga adalah prima ditunjukkan oleh Dean [5].  Hasil lainnya tentang graf prima dapat dilihat di [6], [7], [8].
Penelitian terkait pelabelan koprima pada beberapa kelas graf ataupun graf hasil operasi, antara lain: Asplund dan Fox [9] memberikan bilangan koprima terkecil dari graf roda 𝑊𝑊 𝑛𝑛 , graf lengkap 𝐾𝐾 𝑛𝑛 , dan gabungan dari graf lingkaran;  Asplund dan Fox [10]  memberikan  bilangan koprima  terkecil  dari graf prisma dan graf Petersen. Lee [11]  memperoleh  bilangan koprima terkecil pada graf 𝐾𝐾 𝑛𝑛 ⨀ 𝐾𝐾� 2 , dan graf hasil operasi join dari dua graf lintasan dan join dari dua graf lingkaran. Lee, Wui, dan Yeh [12] menunjukkan bahwa graf Amal( 𝐺𝐺 , 𝑣𝑣 0 , 𝑡𝑡 ) merupakan graf prima ketika 𝐺𝐺 adalah graf lintasan, graf lingkaran, atau graf roda genap. Mereka juga menunjukkan bahwa graf amalgamasi pada graf roda ganjil merupakan graf koprima. Komarullah, Slamin, dan Wijaya [13] memberikan bilangan koprima terkecil dari amalgamasi pada graf roda ganjil. Hasil selengkapnya mengenai graf prima dan koprima dapat dilihat di Gallian [14].
Misalkan ditetapkan titik 𝑣𝑣 0 dari graf 𝐺𝐺 . Lee, Wui, dan Yeh [12] mendefinisikan amalgamasi 𝑡𝑡 salinan graf 𝐺𝐺 pada titik terminal 𝑣𝑣 0 , dinotasikan Amal( 𝐺𝐺 , 𝑣𝑣 0 , 𝑡𝑡 ), adalah graf yang diperoleh dari 𝑡𝑡 salinan 𝐺𝐺 yang diidentifikasi pada titik amalgamasi 𝑣𝑣 0 (yaitu setiap titik 𝑣𝑣 0 di 𝐺𝐺 dilekatkan atau dilebur  menjadi satu  titik).  Dengan demikian graf hasil operasi amalgamasi bergantung pada pemilihan titik amalgamasinya. Untuk graf regular, tentu saja hal ini tidak berlaku. Jika 𝐺𝐺 berorde 𝑛𝑛 , maka Amal( 𝐺𝐺 , 𝑣𝑣 0 , 𝑡𝑡 ) berorde ( 𝑛𝑛 − 1) 𝑡𝑡 + 1 .
Pada paper ini dibahas bilangan koprima  terkecil  dari graf hasil amalgamasi  pada  graf lengkap 𝐾𝐾 𝑛𝑛 , yaitu Amal( 𝐾𝐾 𝑛𝑛 , 𝑣𝑣 , 𝑡𝑡 ), untuk sebarang titik 𝑣𝑣 di 𝐾𝐾 𝑛𝑛 dan bilangan bulat 𝑛𝑛 ≥ 4 ; bilangan koprima terkecil dari graf berlian 𝐵𝐵𝑟𝑟 𝑛𝑛 untuk setiap bilangan bulat 𝑛𝑛 ≥ 3 ; dan bilangan koprima terkecil dari  graf Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ), dengan titik amalgamasi 𝑣𝑣 0 yaitu titik berderajat 𝑛𝑛 di 𝐵𝐵𝑟𝑟 𝑛𝑛 untuk setiap 3 ≤ 𝑛𝑛 ≤ 10 dan juga untuk setiap 𝑛𝑛 ≥ 11 ganjil.  Graf lengkap dengan 𝑛𝑛 titik, dinotasikan 𝐾𝐾 𝑛𝑛 , adalah graf yang setiap dua titiknya bertetangga. Hinding dkk.  [15] mendefinisikan graf berlian dengan order 2 𝑛𝑛 ,  dinotasikan dengan 𝐵𝐵𝑟𝑟 𝑛𝑛 , sebagai graf dengan himpunan titik 𝑉𝑉 ( 𝐵𝐵𝑟𝑟 𝑛𝑛 ) = { 𝑣𝑣 0 } ∪ { 𝑣𝑣 𝑖𝑖 | 𝑖𝑖 ∈ [1, 𝑛𝑛 ]} ∪ { 𝑢𝑢 𝑖𝑖 | 𝑖𝑖 ∈ [1, 𝑛𝑛 − 1]} dan himpunan sisi

## 3
𝐸𝐸 ( 𝐵𝐵𝑟𝑟 𝑛𝑛 ) = { 𝑣𝑣 0 𝑣𝑣 𝑖𝑖 | 𝑖𝑖 ∈ [1, 𝑛𝑛 ]} ∪ { 𝑣𝑣 𝑖𝑖 𝑣𝑣 𝑖𝑖+1 , 𝑢𝑢 𝑖𝑖 𝑣𝑣 𝑖𝑖+1 , 𝑢𝑢 𝑖𝑖 𝑣𝑣 𝑖𝑖 | 𝑖𝑖 ∈ [1, 𝑛𝑛 − 1]} ∪ { 𝑢𝑢 𝑖𝑖 𝑢𝑢 𝑖𝑖+1 | 𝑖𝑖 ∈ [1, 𝑛𝑛 − 2]} sebagaimana diperlihatkan pada Gambar 1.
Gambar 1. Graf berlian 𝐵𝐵𝑟𝑟 𝑛𝑛 dan notasi titiknya

## 2 Metode Penelitian
Berdasarkan definisi pelabelan koprima, langkah-langkah untuk mendapatkan bilangan koprima terkecil pada suatu graf 𝐺𝐺 sebagai berikut.
1) Mengecek bahwa 𝐺𝐺 bukan graf prima. Hal ini dapat dilakukan dengan studi literatur, dengan melihat hasil penelitian tentang graf prima. Jika belum ada penelitian terkait graf yang dimaksud, apakah prima atau bukan, maka harus dicek apakah label 1 sampai 𝑛𝑛 dapat diberikan pada titik-titik di 𝐺𝐺 sedemikian sehingga setiap dua titik yang bertetangga mempunyai label yang relatif prima.
2) Mengklaim 𝔭𝔭𝔭𝔭 ( 𝐺𝐺 ) = 𝑘𝑘 dengan 𝑘𝑘 > 𝑛𝑛 . Tentu saja klaim ini dilakukan setelah dilakukan proses perhitungan dengan seksama. Selanjutnya  dibuktikan bahwa 𝔭𝔭𝔭𝔭 ( 𝐺𝐺 ) ≥ 𝑘𝑘 dan 𝔭𝔭𝔭𝔭 ( 𝐺𝐺 ) ≤ 𝑘𝑘 . Pembuktian bahwa 𝔭𝔭𝔭𝔭 ( 𝐺𝐺 ) ≥ 𝑘𝑘 adalah dengan memperhatikan struktur kelas graf yang dikaji dan sifat-sifat dua bilangan bulat yang relatif prima. Sedangkan pembuktian bahwa 𝔭𝔭𝔭𝔭 ( 𝐺𝐺 ) ≤ 𝑘𝑘 adalah dengan mendefinisikan pelabelan koprima pada graf 𝐺𝐺 dengan label dari 1 sampai 𝑘𝑘 . Pada penelitian ini, karena 1 relatif prima dengan sebarang bilangan bulat positif, maka titik berderajat terbesar dari graf 𝐺𝐺 diberi label 1.
Berikut ini diberikan beberapa lema tentang dua bilangan bulat positif yang saling relatif prima.
Lema 1 Misalkan 𝑎𝑎 dan 𝑏𝑏 bilangan bulat positif.
a) Jika 𝑎𝑎 dan 𝑏𝑏 konsekutif, maka 𝑎𝑎 dan 𝑏𝑏 relatif prima [16] .
b) Jika 𝑎𝑎 dan 𝑏𝑏 relatif prima, maka terdapat dua bilangan bulat 𝑥𝑥 dan 𝑦𝑦 sedemikian sehingga 𝑎𝑎𝑥𝑥 + 𝑏𝑏𝑦𝑦 = 1 [16] .
c) Jika 𝑎𝑎 = 1 (mod  2) maka terdapat bilangan bulat positif 𝑟𝑟 yang tidak memiliki faktor ganjil selain satu sedemikian sehingga gcd( 𝑎𝑎 , 𝑎𝑎 + 𝑟𝑟 ) = 1 [13] .

## 4 Pelabelan Koprima Pada Amalgamasi Graf Lengkap dan Graf Berlian

## 3  Hasil dan Pembahasan
Pada bagian ini dibahas tentang bilangan koprima terkecil pada graf Amal( 𝐺𝐺 , 𝑣𝑣 0 , 𝑡𝑡 ) dengan 𝐺𝐺 merupakan graf lengkap dan graf berlian. Pada paper ini, titik berderajat 𝑛𝑛 dari graf berlian dipilih sebagai titik amalgamasi . Pertama, dijelaskan tentang pelabelan koprima dari graf hasil operasi amalgamasi pada graf lengkap, Amal( 𝐾𝐾 𝑛𝑛 , 𝑣𝑣 , 𝑡𝑡 ) ,  dengan 𝑛𝑛 > 3. Graf Amal( 𝐾𝐾 𝑛𝑛 , 𝑣𝑣 , 𝑡𝑡 ) mempunyai ( 𝑛𝑛 − 1) 𝑡𝑡 + 1 titik. Misalkan himpunan titik dan sisi pada graf Amal( 𝐾𝐾 𝑛𝑛 , 𝑣𝑣 , 𝑡𝑡 ) secara berturut-turut adalah 𝑉𝑉� Amal( 𝐾𝐾 𝑛𝑛 , 𝑣𝑣 , 𝑡𝑡 ) � = { 𝑣𝑣 } ∪ { 𝑣𝑣 𝑖𝑖𝑖𝑖 | 𝑖𝑖 ∈ [1, 𝑡𝑡 ] dan 𝑗𝑗 ∈ [1, 𝑛𝑛 − 1]} dan 𝐸𝐸� Amal( 𝐾𝐾 𝑛𝑛 , 𝑣𝑣 , 𝑡𝑡 ) � = �𝑣𝑣𝑣𝑣 𝑖𝑖𝑖𝑖 , 𝑣𝑣 𝑖𝑖𝑖𝑖 𝑣𝑣 𝑖𝑖𝑖𝑖 � 𝑖𝑖 ∈ [1, 𝑡𝑡 ] dan 𝑗𝑗 , 𝑟𝑟 ∈ [1, 𝑛𝑛 − 1] tetapi 𝑗𝑗 ≠ 𝑟𝑟� .
Teorema  2 Untuk setiap bilangan bulat 𝑛𝑛 ≥ 4 dan 𝑡𝑡 ≥ 2 dan 𝑣𝑣 ∈ 𝑉𝑉 ( 𝐾𝐾 𝑛𝑛 ) ,  bilangan koprima terkecil dari graf Amal( 𝐾𝐾 𝑛𝑛 , 𝑣𝑣 , 𝑡𝑡 ) sebagai berikut:
𝔭𝔭𝔭𝔭� Amal( 𝐾𝐾 𝑛𝑛 , 𝑣𝑣 , 𝑡𝑡 ) � = � 4 𝑡𝑡 + 1, untuk 𝑛𝑛 = 4, 𝑝𝑝 (( 𝑛𝑛−3 ) 𝑡𝑡+2 ) , untuk 𝑛𝑛 ≥ 5,
dengan 𝑝𝑝 (( 𝑛𝑛−3 ) 𝑡𝑡+2 ) adalah � ( 𝑛𝑛 − 3) 𝑡𝑡 + 2 � bilangan prima pertama.
Bukti. Pertama akan ditunjukkan 𝔭𝔭𝔭𝔭 (Amal( 𝐾𝐾 4 , 𝑣𝑣 , 𝑡𝑡 )) ≥ 4 𝑡𝑡 + 1. Misalkan titik amalgamasi 𝑣𝑣 diberi label 1. Dengan demikian label 𝑣𝑣 relatif prima dengan setiap label titik 𝑣𝑣 𝑖𝑖𝑖𝑖 . Titik 𝑣𝑣 𝑖𝑖𝑖𝑖 membutuhkan 2 𝑡𝑡 label ganjil dan 𝑡𝑡 label genap. Jelas bahwa banyaknya label ganjil yang tersedia pada himpunan {1, 2, … , 3 𝑡𝑡 + 1} kurang dari 2 𝑡𝑡 + 1. Karena terdapat 2 𝑡𝑡 + 1 label ganjil pada himpunan {1, 2, … , 4 𝑡𝑡 + 1}, maka 𝔭𝔭𝔭𝔭 (Amal( 𝐾𝐾 4 , 𝑣𝑣 , 𝑡𝑡 )) ≥ 4 𝑡𝑡 + 1. Selanjutnya akan dibuktikan 𝔭𝔭𝔭𝔭 (Amal( 𝐾𝐾 4 , 𝑣𝑣 , 𝑡𝑡 )) ≤ 4 𝑡𝑡 + 1, yaitu dengan membangun pelabelan koprima pada graf Amal( 𝐾𝐾 4 , 𝑣𝑣 , 𝑡𝑡 ) . Misalkan fungsi 𝑓𝑓 : 𝑉𝑉 (Amal( 𝐾𝐾 4 , 𝑣𝑣 , 𝑡𝑡 )) → {1, 2, . . . , 4 𝑡𝑡 + 1} didefinisikan sebagai berikut. Untuk setiap 𝑖𝑖 = 1, 2, … , 𝑡𝑡 ,
𝑓𝑓 ( 𝑣𝑣 ) = 1 dan 𝑓𝑓�𝑣𝑣 𝑖𝑖𝑖𝑖 � = � 2 𝑖𝑖 , untuk 𝑗𝑗 = 1, 4 𝑖𝑖 − 1, untuk 𝑗𝑗 = 2, 4 𝑖𝑖 + 1, untuk 𝑗𝑗 = 3.
Berdasarkan definisi pelabelan koprima, setiap titik yang bertetangga harus relatif prima. Hal ini ditunjukkan sebagai berikut.
• Jelas bahwa gcd( 𝑣𝑣 𝑖𝑖1 , 𝑣𝑣 𝑖𝑖2 ) = gcd(2 𝑖𝑖 , 4 𝑖𝑖 − 1) = 1, karena 2 𝑖𝑖 bilangan genap, sedangkan 4 𝑖𝑖 − 1 bilangan ganjil untuk setiap 𝑖𝑖 ∈ [1, 𝑡𝑡 ] . Demikian juga gcd( 𝑣𝑣 𝑖𝑖1 , 𝑣𝑣 𝑖𝑖3 ) = gcd(2 𝑖𝑖 , 4 𝑖𝑖 + 1) = 1.
• Perhatikan label titik 𝑣𝑣 𝑖𝑖2 dan 𝑣𝑣 𝑖𝑖3 untuk setiap 𝑖𝑖 ∈ [1, 𝑡𝑡 ] . Karena kedua label 4 𝑖𝑖 − 1 dan 4 𝑖𝑖 + 1 bernilai ganjil dan |(4 𝑖𝑖 − 1) − (4 𝑖𝑖 + 1)| = 2 , berdasarkan Lema 1(iii)  didapatkan gcd( 𝑓𝑓 ( 𝑣𝑣 𝑖𝑖2 ), 𝑓𝑓 ( 𝑣𝑣 𝑖𝑖3 )) = gcd(4 𝑖𝑖 − 1, 4 𝑖𝑖 + 1) = 1 .  Jadi  titik 𝑣𝑣 𝑖𝑖2 dan 𝑣𝑣 𝑖𝑖3 mempunyai label yang relatif prima.

## 5
Dengan demikian terbukti bahwa fungsi 𝑓𝑓 memenuhi kaidah pelabelan koprima, sehingga 𝔭𝔭𝔭𝔭 (Amal( 𝐾𝐾 4 , 𝑣𝑣 , 𝑡𝑡 )) ≤ 4 𝑡𝑡 + 1 . Jadi, 𝔭𝔭𝔭𝔭 (Amal( 𝐾𝐾 4 , 𝑣𝑣 , 𝑡𝑡 )) = 4 𝑡𝑡 + 1 .
Untuk 𝑛𝑛 ≥ 5, akan ditunjukkan bahwa 𝔭𝔭𝔭𝔭� Amal( 𝐾𝐾 𝑛𝑛 , 𝑣𝑣 , 𝑡𝑡 ) � ≥ 𝑝𝑝 � ( 𝑛𝑛−3 ) 𝑡𝑡+2� , dengan 𝑝𝑝 � ( 𝑛𝑛−3 ) 𝑡𝑡+2� adalah � ( 𝑛𝑛 − 3) 𝑡𝑡 + 2 � bilangan prima pertama. Misalkan titik amalgamasi pada graf Amal( 𝐾𝐾 𝑛𝑛 , 𝑣𝑣 , 𝑡𝑡 ) diberi label 1 , maka tersisa ( 𝑛𝑛 − 1) 𝑡𝑡 titik yang belum diberi label. Setiap titik 𝑣𝑣 𝑖𝑖𝑖𝑖 yang berada pada sebuah graf 𝐾𝐾 𝑛𝑛 dapat dilabeli dengan sebuah label genap, sebuah label ganjil dan ( 𝑛𝑛 − 3) titik sisanya harus mendapatkan label bilangan prima  selain 2 dan 3. Sehingga dibutuhkan ( 𝑛𝑛 − 3) 𝑡𝑡 bilangan prima selain 2 dan 3 untuk melabeli keseluruhan titik 𝑣𝑣 𝑖𝑖𝑖𝑖 . Maka 𝔭𝔭𝔭𝔭� Amal( 𝐾𝐾 𝑛𝑛 , 𝑣𝑣 , 𝑡𝑡 ) � ≥ 𝑝𝑝 (( 𝑛𝑛−3 ) 𝑡𝑡+2 ) untuk 𝑛𝑛 ≥ 5.
Selanjutnya akan dibuktikan 𝔭𝔭𝔭𝔭� Amal( 𝐾𝐾 𝑛𝑛 , 𝑣𝑣 , 𝑡𝑡 ) � ≤ 𝑝𝑝 (( 𝑛𝑛−3 ) 𝑡𝑡+2 ) yaitu dengan membangun pelabelan koprima pada graf Amal( 𝐾𝐾 𝑛𝑛 , 𝑣𝑣 , 𝑡𝑡 ) . Definisikan fungsi 𝑓𝑓 : 𝑉𝑉� Amal( 𝐾𝐾 𝑛𝑛 , 𝑣𝑣 , 𝑡𝑡 ) � → {1,2, . . . , 𝑝𝑝 (( 𝑛𝑛−3 ) 𝑡𝑡+2 )) } sebagai berikut. Untuk setiap 𝑖𝑖 ∈ [1, 𝑡𝑡 ] ,
𝑓𝑓 ( 𝑣𝑣 ) = 1 dan 𝑓𝑓�𝑣𝑣 𝑖𝑖𝑖𝑖 � = � 6 𝑖𝑖 − 4                 ; 𝑗𝑗 = 1, 6 𝑖𝑖 − 3                   ; 𝑗𝑗 = 2, 𝑝𝑝 � ( 𝑛𝑛−2 ) 𝑖𝑖+2− ( 𝑛𝑛−𝑖𝑖 ) � ; 𝑗𝑗 = 3, 4, … , 𝑛𝑛 − 1.
Karena dalam setiap blok, dua titik berlabel konsekutif dan titik lainya berlabel prima, maka graf Amal( 𝐾𝐾 𝑛𝑛 , 𝑣𝑣 , 𝑡𝑡 ) adalah graf koprima, sehingga 𝔭𝔭𝔭𝔭� Amal( 𝐾𝐾 𝑛𝑛 , 𝑣𝑣 , 𝑡𝑡 ) � ≤ 𝑝𝑝 � ( 𝑛𝑛−3 ) 𝑡𝑡+2� . Jadi, 𝔭𝔭𝔭𝔭� Amal( 𝐾𝐾 𝑛𝑛 , 𝑣𝑣 , 𝑡𝑡 ) � = 𝑝𝑝 (( 𝑛𝑛−3 ) 𝑡𝑡+2 ) untuk 𝑛𝑛 ≥ 5. ∎
Pada Gambar 2 diberikan contoh pelabelan koprima dari graf hasil operasi amalgamasi pada graf lengkap Amal( 𝐾𝐾 4 , 𝑣𝑣 , 4) dan Amal( 𝐾𝐾 6 , 𝑣𝑣 , 4) dengan 𝔭𝔭𝔭𝔭� Amal( 𝐾𝐾 4 , 𝑣𝑣 , 3) � = 13 dan 𝔭𝔭𝔭𝔭� Amal( 𝐾𝐾 6 , 𝑣𝑣 , 4) � = 𝑝𝑝 14 = 43 menggunakan perumusan pelabelan yang diberikan pada pembuktian Teorema 2.
Gambar 2. Pelabelan koprima graf Amal( 𝐾𝐾 4 , 𝑣𝑣 , 4) dan Amal( 𝐾𝐾 6 , 𝑣𝑣 , 4)
Selanjutnya dibahas bilangan koprima terkecil dari graf berlian dan graf hasil amalgamasinya. Penotasian titik graf berlian dapat dilihat pada Gambar 1.

## 6
Teorema 3 Untuk setiap bilangan bulat 𝑛𝑛 ≥ 3 , bilangan koprima terkecil dari graf berlian adalah
𝔭𝔭𝔭𝔭 ( 𝐵𝐵𝑟𝑟 𝑛𝑛 ) = � 3 𝑛𝑛 − 2; untuk 𝑛𝑛 ganjil,
3 𝑛𝑛 − 1; untuk 𝑛𝑛 genap.
Bukti. Misalkan titik amalgamasi 𝑣𝑣 0 diberi label 1 . Jelas label titik 𝑣𝑣 0 relatif prima dengan setiap label titik 𝑣𝑣 𝑖𝑖 . Titik-titik 𝑣𝑣 𝑖𝑖 membutuhkan � 𝑛𝑛 2 � label ganjil dan � 𝑛𝑛 2 � label genap. Keseluruhan titik 𝑢𝑢 𝑖𝑖 memerlukan 𝑛𝑛 − 1 label ganjil. Sehingga graf berlian 𝐵𝐵𝑟𝑟 𝑛𝑛 memerlukan � 3𝑛𝑛 2 � label ganjil. Karena terdapat 3𝑛𝑛−1 2 label ganjil pada himpunan {1,2, . . . ,3 𝑛𝑛 − 2} untuk 𝑛𝑛 ganjil, diperoleh 𝔭𝔭𝔭𝔭 ( 𝐵𝐵𝑟𝑟 𝑛𝑛 ) ≥ 3 𝑛𝑛 − 2. Di  sisi lain, terdapat 3𝑛𝑛 2 label ganjil pada himpunan {1,2, . . . ,3 𝑛𝑛 − 1} untuk 𝑛𝑛 genap, sehingga 𝔭𝔭𝔭𝔭 ( 𝐵𝐵𝑟𝑟 𝑛𝑛 ) ≥ 3 𝑛𝑛 − 1.
Untuk 𝑛𝑛 ganjil, pembuktian bahwa 𝔭𝔭𝔭𝔭 ( 𝐵𝐵𝑟𝑟 𝑛𝑛 ) ≤ 3 𝑛𝑛 − 2 dilakukan dengan dibangunnya pelabelan koprima pada graf berlian 𝐵𝐵𝑟𝑟 𝑛𝑛 . Definisikan fungsi 𝑓𝑓 : 𝑉𝑉 ( 𝐵𝐵𝑟𝑟 𝑛𝑛 ) → {1, 2, . . . , 3 𝑛𝑛 − 2} untuk
𝑖𝑖 = 1, 2, … , 𝑛𝑛 sebagai berikut.
𝑓𝑓 ( 𝑣𝑣 0 ) = 1, 𝑓𝑓 ( 𝑣𝑣 𝑖𝑖 ) = � 3 𝑖𝑖 − 1; 𝑖𝑖 ≠ 𝑛𝑛 , 3 𝑛𝑛 − 3; 𝑖𝑖 = 𝑛𝑛 , dan 𝑓𝑓 ( 𝑢𝑢 𝑖𝑖 ) = � 3 𝑖𝑖 ; untuk 𝑖𝑖 ganjil,
3 𝑖𝑖 + 1; untuk 𝑖𝑖 genap.
Berdasarkan pendefinisian ini diperolah bahwa setiap dua titik yang bertetangga mempunyai label yang relatif prima. Hal tersebut ditunjukkan sebagai berikut.
• Diketahui bahwa bilangan 3 𝑖𝑖 − 1 ada dalam kelas 2 (mod 3) . Dengan demikian jelas bahwa label titik 𝑣𝑣 𝑖𝑖 dan 𝑣𝑣 𝑖𝑖+1 relatif prima untuk setiap 𝑖𝑖 ∈ 1,2, . . . , 𝑛𝑛 − 2 .
• Beberapa pasangan titik yang bertetangga labelnya konsekutif, sehingga relatif prima (menurut Lema 1(i)), yaitu pasangan titik ( 𝑣𝑣 𝑛𝑛−1 , 𝑣𝑣 𝑛𝑛 ), ( 𝑢𝑢 𝑛𝑛−1 , 𝑣𝑣 𝑛𝑛 ), dan ( 𝑢𝑢 𝑖𝑖 , 𝑣𝑣 𝑖𝑖 ) dengan 𝑖𝑖 ganjil.
• Perhatikan label titik 𝑢𝑢 𝑖𝑖 dan 𝑢𝑢 𝑖𝑖+1 untuk 𝑖𝑖 genap. Karena 3 𝑖𝑖 + 3 bernilai ganjil dan |(3 𝑖𝑖 + 1) − (3 𝑖𝑖 + 3)| = 2 , menurut Lema 1(iii) diperoleh gcd �𝑓𝑓 ( 𝑢𝑢 𝑖𝑖 ), 𝑓𝑓 ( 𝑢𝑢 𝑖𝑖+1 ) � = gcd(3 𝑖𝑖 + 1, 3 𝑖𝑖 + 3) = 1 .
• Perhatikan label titik 𝑢𝑢 𝑖𝑖 dan 𝑢𝑢 𝑖𝑖+1 untuk 𝑖𝑖 ganjil. Karena 3 𝑖𝑖 bernilai ganjil dan |(3 𝑖𝑖 ) − (3 𝑖𝑖 + 4)| = 4 , berdasarkan Lema 1(iii) diperoleh gcd( 𝑓𝑓 ( 𝑢𝑢 𝑖𝑖 ), 𝑓𝑓 ( 𝑢𝑢 𝑖𝑖+1 )) = gcd(3 𝑖𝑖 , 3 𝑖𝑖 + 4) = 1 .
• Perhatikan label titik 𝑢𝑢 𝑖𝑖 dan 𝑣𝑣 𝑖𝑖+1 untuk 𝑖𝑖 ganjil. Karena 3 𝑖𝑖 dan 3 𝑖𝑖 + 2 bernilai ganjil dan |3 𝑖𝑖 −
(3 𝑖𝑖 + 2)| = 2 , menurut Lema 1(iii) diperoleh gcd( 𝑓𝑓 ( 𝑢𝑢 𝑖𝑖 ), 𝑓𝑓 ( 𝑢𝑢 𝑖𝑖+1 )) = gcd(3 𝑖𝑖 , 3 𝑖𝑖 + 2) = 1 .
• Perhatikan label titik 𝑢𝑢 𝑖𝑖 dan 𝑣𝑣 𝑖𝑖 untuk 𝑖𝑖 genap. Karena kedua 3 𝑖𝑖 + 1 dan 3 𝑖𝑖 − 1 bernilai ganjil serta |(3 𝑖𝑖 + 1) − (3 𝑖𝑖 − 1)| = 2 , berdasarkan Lema 1(iii) diperoleh gcd( 𝑓𝑓 ( 𝑢𝑢 𝑖𝑖 ), 𝑓𝑓 ( 𝑣𝑣 𝑖𝑖 )) = gcd(3 𝑖𝑖 + 1, 3 𝑖𝑖 − 1) = 1 .
Dengan demikian, fungsi 𝑓𝑓 memenuhi aturan pelabelan koprima, sehingga 𝔭𝔭𝔭𝔭 ( 𝐵𝐵𝑟𝑟 𝑛𝑛 ) ≤ 3 𝑛𝑛 − 2 . Jadi, 𝔭𝔭𝔭𝔭 ( 𝐵𝐵𝑟𝑟 𝑛𝑛 ) = 3 𝑛𝑛 − 2 untuk 𝑛𝑛 ganjil.
Untuk 𝑛𝑛 genap, definisikan fungsi 𝑓𝑓 : 𝑉𝑉 ( 𝐵𝐵𝑟𝑟 𝑛𝑛 ) → {1, 2, . . . , 3 𝑛𝑛 − 1} sebagai berikut.
Untuk 𝑖𝑖 ∈ 1, 2, … , 𝑛𝑛 ,
𝑓𝑓 ( 𝑣𝑣 0 ) = 1; 𝑓𝑓 ( 𝑣𝑣 𝑖𝑖 ) = 3 𝑖𝑖 − 1; dan 𝑓𝑓 ( 𝑢𝑢 𝑖𝑖 ) = � 3 𝑖𝑖 ; untuk 𝑖𝑖 ganjil, 3 𝑖𝑖 + 1; untuk 𝑖𝑖 genap.
Dengan cara yang sama seperti pada 𝑛𝑛 ganjil, dapat ditunjukkan bahwa label dari setiap dua titik yang bertetangga relatif prima. Oleh karena itu, fungsi 𝑓𝑓 memenuhi kaidah pelabelan koprima, sehingga 𝔭𝔭𝔭𝔭 ( 𝐵𝐵𝑟𝑟 𝑛𝑛 ) ≤ 3 𝑛𝑛 − 1 . Jadi, 𝔭𝔭𝔭𝔭 ( 𝐵𝐵𝑟𝑟 𝑛𝑛 ) = 3 𝑛𝑛 − 1 untuk 𝑛𝑛 genap. ∎
Pada Gambar 3  diberikan contoh  pelabelan koprima pada graf berlian 𝐵𝐵𝑟𝑟 5 dan 𝐵𝐵𝑟𝑟 6 dengan 𝔭𝔭𝔭𝔭 ( 𝐵𝐵𝑟𝑟 5 ) = 13 dan 𝔭𝔭𝔭𝔭 ( 𝐵𝐵𝑟𝑟 6 ) = 17 .
Gambar 3. Pelabelan koprima pada graf 𝐵𝐵𝑟𝑟 5 dan 𝐵𝐵𝑟𝑟 6 Misalkan 𝑣𝑣 0 adalah titik berderajat 𝑛𝑛 di 𝐵𝐵𝑟𝑟 𝑛𝑛 . Graf Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) mempunyai (2 𝑛𝑛 − 1) 𝑡𝑡 + 1 titik. Misalkan himpunan titik dan sisi dari  graf Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) untuk setiap 𝑖𝑖 ∈ [1, 𝑡𝑡 ] secara berturut-turut adalah 𝑉𝑉� Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) � = { 𝑣𝑣 0 } ∪ �𝑣𝑣 𝑖𝑖𝑖𝑖 �𝑗𝑗 ∈ [1, 𝑛𝑛 ] � ∪ { 𝑢𝑢 𝑖𝑖𝑖𝑖 | 𝑗𝑗 ∈ [1, 𝑛𝑛 − 1]} dan 𝐸𝐸� Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) � = �𝑣𝑣 0 𝑣𝑣 𝑖𝑖𝑖𝑖 � 𝑗𝑗 ∈ [1, 𝑛𝑛 ] � ∪ �𝑣𝑣 𝑖𝑖𝑖𝑖 𝑣𝑣 𝑖𝑖𝑖𝑖+1 , 𝑢𝑢 𝑖𝑖𝑖𝑖 𝑣𝑣 𝑖𝑖𝑖𝑖 , 𝑢𝑢 𝑖𝑖𝑖𝑖 𝑣𝑣 𝑖𝑖𝑖𝑖+1 � 𝑗𝑗 ∈ [1, 𝑛𝑛 − 1] � ∪ �𝑢𝑢 𝑖𝑖𝑖𝑖 𝑢𝑢 𝑖𝑖𝑖𝑖+1 �𝑗𝑗 ∈ [1, 𝑛𝑛 − 2] � . Gambar  4  merupakan ilustrasi penotasian titik dan sisi dari graf Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) .
Gambar 4. Penotasian titik dan sisi dari graf Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 )
Teorema 4 Misalkan 𝑣𝑣 0 adalah titik berderajat 𝑛𝑛 pada graf 𝐵𝐵𝑟𝑟 𝑛𝑛 . Untuk setiap bilangan bulat 𝑡𝑡 ≥ 2 dan 𝑛𝑛 ≥ 3 ganjil, 𝔭𝔭𝔭𝔭 (Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 )) = (3 𝑛𝑛 − 3) 𝑡𝑡 + 1.

## 8
Bukti. Pertama  akan ditunjukkan 𝔭𝔭𝔭𝔭� Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) � ≥ (3 𝑛𝑛 − 3) 𝑡𝑡 + 1 . Graf Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) membutuhkan ( 3𝑛𝑛−1 ) 𝑡𝑡+2 2 label ganjil dan ( 𝑛𝑛−1 ) 𝑡𝑡 2 label genap. Karena terdapat ( 3𝑛𝑛−1 ) 𝑡𝑡+2 2 bilangan ganjil pada himpunan {1,2, … , (3 𝑛𝑛 − 3) 𝑡𝑡 + 1} , maka 𝔭𝔭𝔭𝔭� Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) � ≥ (3 𝑛𝑛 − 3) 𝑡𝑡 + 1.
Selanjutnya untuk setiap 𝑖𝑖 = 1, 2, … , 𝑡𝑡 definisikan fungsi 𝑓𝑓 : 𝑉𝑉� Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) � → {1, 2, . . . , (3 𝑛𝑛 − 3) 𝑡𝑡 + 1} sebagai berikut.
𝑓𝑓 ( 𝑣𝑣 0 ) = 1 ,
𝑓𝑓�𝑣𝑣 𝑖𝑖𝑖𝑖 � = � 3 𝑛𝑛 ( 𝑖𝑖 − 1) + 3( 𝑗𝑗 − 𝑖𝑖 ) + 2; untuk 𝑗𝑗 = 1, 2, … , 𝑛𝑛 − 1, 3 𝑖𝑖 ( 𝑛𝑛 − 1)                            ; untuk 𝑗𝑗 = 𝑛𝑛 ,
𝑓𝑓�𝑢𝑢 𝑖𝑖𝑖𝑖 � = � 3 𝑛𝑛 ( 𝑖𝑖 − 1) + 3( 𝑗𝑗 − 𝑖𝑖 ) + 3; untuk 𝑗𝑗 ganjil,
3 𝑛𝑛 ( 𝑖𝑖 − 1) + 3( 𝑗𝑗 − 𝑖𝑖 ) + 4; untuk 𝑗𝑗 genap.
Akan ditunjukkan pada pendefinisian label di atas, setiap dua titik yang bertetangga mendapat label yang relatif prima, sebagai berikut.
• Jelas bahwa label titik 𝑣𝑣 𝑖𝑖𝑖𝑖 dan 𝑣𝑣 𝑖𝑖𝑖𝑖+1 untuk 𝑗𝑗 = 1,2, . . . , 𝑛𝑛 − 2 relatif prima.
• Perhatikan bahwa label titik 𝑢𝑢 𝑖𝑖𝑖𝑖 bernilai ganjil untuk setiap 𝑖𝑖 dan 𝑗𝑗 . Untuk 𝑗𝑗 ganjil, diperoleh 𝑓𝑓�𝑣𝑣 𝑖𝑖𝑖𝑖+1 � = 𝑓𝑓�𝑢𝑢 𝑖𝑖𝑖𝑖 � + 4 dan 𝑓𝑓�𝑣𝑣 𝑖𝑖𝑖𝑖+1 � = 𝑓𝑓�𝑢𝑢 𝑖𝑖𝑖𝑖 � + 2. Sedangkan untuk 𝑗𝑗 genap, 𝑓𝑓�𝑢𝑢 𝑖𝑖𝑖𝑖+1 � = 𝑓𝑓�𝑢𝑢 𝑖𝑖𝑖𝑖 � + 2 dan 𝑓𝑓�𝑢𝑢 𝑖𝑖𝑖𝑖 � = 𝑓𝑓�𝑣𝑣 𝑖𝑖𝑖𝑖 � + 2. Berdasarkan Lema 1(iii), label dari pasangan titik-titik tersebut relatif prima.
• Tiga pasangan titik ( 𝑣𝑣 𝑖𝑖𝑛𝑛−1 , 𝑣𝑣 𝑖𝑖𝑛𝑛 ), ( 𝑢𝑢 𝑖𝑖1 , 𝑣𝑣 𝑖𝑖1 ) , dan ( 𝑢𝑢 𝑖𝑖𝑛𝑛−1 , 𝑣𝑣 𝑖𝑖𝑛𝑛 ) mempunyai label konsekutif. Oleh karena itu, label pasangan titik-titik tersebut relatif prima.
Jadi  fungsi 𝑓𝑓 memenuhi aturan  pelabelan koprima, sehingga 𝔭𝔭𝔭𝔭� Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) � ≤ (3 𝑛𝑛 − 3) 𝑡𝑡 + 1 . Dengan demikian 𝔭𝔭𝔭𝔭� Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) � = (3 𝑛𝑛 − 3) 𝑡𝑡 + 1 . ∎ Pada  Gambar  5  diberikan  contoh pelabelan koprima pada graf Amal( 𝐵𝐵𝑟𝑟 5 , 𝑣𝑣 0 , 3) dengan 𝔭𝔭𝔭𝔭� Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) � = 37.
Gambar 5. Pelabelan koprima pada graf Amal( 𝐵𝐵𝑟𝑟 5 , 𝑣𝑣 0 , 3)

## 9
Misalkan 𝑣𝑣 0 adalah titik berderajat 𝑛𝑛 pada graf berlian 𝐵𝐵𝑟𝑟 𝑛𝑛 . Bilangan koprima terkecil pada graf Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) untuk 𝑛𝑛 genap memiliki batas bawah sebagai berikut.
Lema 5 Untuk setiap bilangan bulat 𝑡𝑡 ≥ 1 dan 𝑛𝑛 genap, jika 𝑣𝑣 0 adalah titik berderajat 𝑛𝑛 pada graf berlian 𝐵𝐵𝑟𝑟 𝑛𝑛 maka 𝔭𝔭𝔭𝔭 (Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 )) ≥ (3 𝑛𝑛 − 2) 𝑡𝑡 + 1 .
Bukti. Dengan cara yang sama seperti Teorema 4, graf Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) membutuhkan ( 3𝑛𝑛−2 ) 𝑡𝑡+2 2 label ganjil dan 𝑛𝑛𝑡𝑡−4𝑡𝑡 2 label genap. Karena terdapat ( 3𝑛𝑛−2 ) 𝑡𝑡+2 2 bilangan ganjil pada himpunan {1,2, . . . , (3 𝑛𝑛 − 2) 𝑡𝑡 + 1} , maka 𝔭𝔭𝔭𝔭 (Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 )) ≥ (3 𝑛𝑛 − 2) 𝑡𝑡 + 1 . ∎ Pada paper ini, pelabelan dari graf Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) untuk 𝑛𝑛 genap, belum dapat didefinisikan secara umum. Hal ini karena terjadi inkonsistensi pertukaran label sedemikian sehingga setiap dua titik yang bertetangga mempunyai label relatif prima. Pada lema berikut, dibuktikan bahwa untuk 𝑛𝑛 = 4, 6, 8, 10 ,  graf Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) mempunyai bilangan koprima terkecil sama dengan batas bawahnya.
Lema 6 Untuk setiap bilangan bulat 𝑡𝑡 > 1 dan 𝑛𝑛 ∈ {4, 6, 8, 10}, jika 𝑣𝑣 0 adalah titik berderajat 𝑛𝑛 pada graf berlian 𝐵𝐵𝑟𝑟 𝑛𝑛 maka bilangan koprima terkecil dari graf Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) adalah sama dengan batas bawahnya, yaitu 𝔭𝔭𝔭𝔭� Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) � = (3 𝑛𝑛 − 2) 𝑡𝑡 + 1.
Bukti. Berdasarkan Lema 5 didapatkan 𝔭𝔭𝔭𝔭� Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) � ≥ (3 𝑛𝑛 − 2) 𝑡𝑡 + 1. Selanjutnya untuk 𝑛𝑛 = 4, 6, 8, 10 akan ditunjukkan 𝔭𝔭𝔭𝔭� Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) � ≤ (3 𝑛𝑛 − 2) 𝑡𝑡 + 1. Definisikan fungsi 𝑓𝑓 : 𝑉𝑉� Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) � → {1, 2, . . . , 10 𝑡𝑡 + 1} sebagai berikut.
𝑓𝑓 ( 𝑣𝑣 0 ) = 1 dan 𝑓𝑓�𝑢𝑢 𝑖𝑖𝑖𝑖 � = � (3 𝑛𝑛 − 2) 𝑖𝑖 + 3 𝑗𝑗 − (3 𝑛𝑛 − 2);   untuk 𝑗𝑗 ganjil,
(3 𝑛𝑛 − 2) 𝑖𝑖 + 3 𝑗𝑗 − (3 𝑛𝑛 − 3);   untuk 𝑗𝑗 genap.
Untuk label titik 𝑣𝑣 𝑖𝑖𝑖𝑖 akan dibedakan menjadi dua kasus sebagai berikut.
1) Untuk 𝑖𝑖 ≠ 2 (mod 3) ,
𝑓𝑓�𝑣𝑣 𝑖𝑖𝑖𝑖 � = (3 𝑛𝑛 − 2) 𝑖𝑖 + 3 𝑗𝑗 − (3 𝑛𝑛 − 1).
2) Untuk 𝑖𝑖 = 2 (mod 3) , dibedakan dalam dua kasus berikut.
a) Untuk 𝑛𝑛 = 4 , 𝑓𝑓�𝑣𝑣 𝑖𝑖𝑖𝑖 � = � 10 𝑖𝑖 + 𝑗𝑗 − 7; untuk 𝑗𝑗 = 1,2,3, 10 𝑖𝑖 + 1      ; untuk 𝑗𝑗 = 4. b) Untuk 𝑛𝑛 = 6, 8, 10, label titik 𝑣𝑣 𝑖𝑖𝑖𝑖 dibagi dua kasus, yaitu jika 𝑗𝑗 genap dan 𝑗𝑗 ganjil.
Jika 𝑗𝑗 genap,
𝑓𝑓�𝑣𝑣 𝑖𝑖𝑖𝑖 � = (3 𝑛𝑛 − 2) 𝑖𝑖 + 3 𝑗𝑗 − (3 𝑛𝑛 − 1),
sedangkan jika 𝑗𝑗 ganjil, ada beberapa kasus untuk 𝑛𝑛 , sebagai berikut.
i) Untuk 𝑛𝑛 = 6 ,
𝑓𝑓�𝑣𝑣 𝑖𝑖𝑖𝑖 � = � 16 𝑖𝑖 + 3 𝑗𝑗 − 19, untuk 𝑖𝑖 = 0 (mod 5) dan 𝑗𝑗 = 5,
16 𝑖𝑖 + 3 𝑗𝑗 − 19, untuk 𝑖𝑖 = 1 (mod 5) dan 𝑗𝑗 = 3,
16 𝑖𝑖 + 3 𝑗𝑗 − 15, untuk 𝑖𝑖 dan 𝑗𝑗 yang lain. ii) Untuk 𝑛𝑛 = 8 , 𝑓𝑓�𝑣𝑣 𝑖𝑖𝑖𝑖 � = ⎩ ⎨ ⎧ 22 𝑖𝑖 + 3 𝑗𝑗 − 25, 22 𝑖𝑖 + 3 𝑗𝑗 − 25, 22 𝑖𝑖 + 3 𝑗𝑗 − 25, 22 𝑖𝑖 + 3 𝑗𝑗 − 21, untuk 𝑖𝑖 = 0 (mod 5) dan 𝑗𝑗 = 3, 7, untuk 𝑖𝑖 = 3 (mod 5) dan 𝑗𝑗 = 5, untuk 𝑖𝑖 ≠ 0, 3 (mod 5) dan 𝑗𝑗 = 3, untuk 𝑖𝑖 dan 𝑗𝑗 yang lain. iii) Untuk 𝑛𝑛 = 10 , 𝑓𝑓�𝑣𝑣 𝑖𝑖𝑖𝑖 � = ⎩ ⎨ ⎧ 28 𝑖𝑖 + 3 𝑗𝑗 − 31,
22 𝑖𝑖 + 3 𝑗𝑗 − 31,
22 𝑖𝑖 + 3 𝑗𝑗 − 31,
22 𝑖𝑖 + 3 𝑗𝑗 − 27, untuk 𝑖𝑖 = 0 (mod 5) dan 𝑗𝑗 = 3, 9, untuk 𝑖𝑖 = 4 (mod 5) dan 𝑗𝑗 = 5,9, untuk 𝑖𝑖 ≠ 0, 4 (mod 5) dan 𝑗𝑗 = 3, 7, untuk 𝑖𝑖 dan 𝑗𝑗 yang lain.
Dengan cara yang sama seperti pada 𝒏𝒏 ganjil, dapat dibuktikan bahwa setiap  dua  titik yang bertetangga mempunyai label yang relatif prima. ∎
Sebagai contoh pelabelan koprima pada graf 𝐀𝐀𝐀𝐀𝐀𝐀𝐀𝐀 ( 𝑩𝑩𝒓𝒓 𝟒𝟒 , 𝒗𝒗 𝟎𝟎 , 𝟒𝟒 ) dan 𝐀𝐀𝐀𝐀𝐀𝐀𝐀𝐀 ( 𝑩𝑩𝒓𝒓 𝟔𝟔 , 𝒗𝒗 𝟎𝟎 , 𝟒𝟒 ) menggunakan rumus pelabelan pada pembuktian Lema 6 diberikan pada Gambar 6.
Gambar 6. Pelabelan koprima pada graf Amal( 𝐵𝐵𝑟𝑟 4 , 𝑣𝑣 0 , 4) dan Amal( 𝐵𝐵𝑟𝑟 6 , 𝑣𝑣 0 , 4)

## 4  Simpulan
Pada paper ini dihasilkan bilangan koprima terkecil dari graf-graf yang dibahas sebagai berikut. Pertama, bilangan koprima terkecil dari graf Amal( 𝐾𝐾 𝑛𝑛 , 𝑣𝑣 , 𝑡𝑡 ) bergantung dari nilai 𝑛𝑛 , untuk 𝑛𝑛 = 4 diperoleh 𝔭𝔭𝔭𝔭 (Amal( 𝐾𝐾 4 , 𝑣𝑣 , 𝑡𝑡 )) = 4 𝑡𝑡 + 1 , sedangkan untuk 𝑛𝑛 > 4 , bilangan koprima terkecilnya adalah � ( 𝑛𝑛 − 3) 𝑡𝑡 + 2 � bilangan prima pertama. Kedua, bilangan koprima terkecil dari graf berlian
a. 𝐴𝐴𝐴𝐴𝑎𝑎𝐴𝐴 ( 𝐵𝐵𝑟𝑟 4 , 𝑣𝑣 0 , 4)
b. 𝐴𝐴𝐴𝐴𝑎𝑎𝐴𝐴 ( 𝐵𝐵𝑟𝑟 6 , 𝑣𝑣 0 , 4)
𝐵𝐵𝑟𝑟 𝑛𝑛 bergantung dari ganjil dan genapnya nilai 𝑛𝑛 , untuk 𝑛𝑛 ganjil, 𝔭𝔭𝔭𝔭 ( 𝐵𝐵𝑟𝑟 𝑛𝑛 ) = 3 𝑛𝑛 − 2 , sedangkan untuk 𝑛𝑛 genap, 𝔭𝔭𝔭𝔭 ( 𝐵𝐵𝑟𝑟 𝑛𝑛 ) = 3 𝑛𝑛 − 1 . Terakhir, bilangan koprima terkecil dari graf Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) juga bergantung dari ganjil dan genapnya nilai 𝑛𝑛 , untuk 𝑛𝑛 ganjil, 𝔭𝔭𝔭𝔭 (Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 )) = (3 𝑛𝑛 − 3) 𝑡𝑡 + 1 , sedangkan untuk 4 ≤ 𝑛𝑛 ≤ 10 genap, 𝔭𝔭𝔭𝔭 (Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 )) = (3 𝑛𝑛 − 2) 𝑡𝑡 + 1 .
Penelitian ini masih menyisakan beberapa masalah terbuka terkait bilangan koprima terkecil pada graf hasil amalgamasi pada graf berlian, antara lain:
1. Tentukan bilangan koprima terkecil dari graf Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 0 , 𝑡𝑡 ) untuk 𝑛𝑛 ≥ 12 genap.
2. Tentukan bilangan koprima terkecil pada graf Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑣𝑣 1 , 2) dan Amal( 𝐵𝐵𝑟𝑟 𝑛𝑛 , 𝑢𝑢 1 , 2) .

## 5  Ucapan Terima Kasih
Penulis mengucapkan terima kasih kepada Kelompok Riset “Graph and Algebra,” Jurusan Matematika, FMIPA Universitas Jember yang memberikan dukungan kepada kami dalam melakukan penelitian ini.

## 6  Daftar Pustaka
[1]  D. M. Burton, Elementary Number Theory , 5th ed. New York: McGraw-Hill, 2002.
[2]  A. H. Berliner, J. Hook, A. Mbirika, N. Dean, A. Marr, and C. D. Mcbee, “Coprime and prime labelings of graphs,” Journal of Integer Sequences , vol. 19, 2016. [Online]. Available: https://cs.uwaterloo.ca/journals/JIS/VOL19/Mbirika/mbi3.pdf
[3]  S. Ashokkumar and S. Maragathavalli, “Prime labelling of some special graphs,” IOSR Journal of Mathematics , vol. 11, no. 1, pp. 1–5, 2015, doi: 10.9790/5728-11110105.
[Online]. Available: https://iosrjournals.org/iosr-jm/papers/Vol11-issue1/Version- 1/A011110105.pdf
[4]  D. M. T. B. Dissanayake, R. A. S. T. Abeysekara, K. D. E. Dhananjaya, A. A. I. Perera, and P. G. R. S. Ranasinghe, “Prime labeling of complete tripartite graphs of the form 𝐾𝐾 1 , 𝑚𝑚 , 𝑛𝑛 ,” vol. 130, pp. 53092–53094, 2019.
[Online]. Available:
https://www.researchgate.net/publication/333357422_Prime_labeling_of_complete_tripart ite_graphs_of_the_form_K_1mn
[5]  N. Dean, “Proof of the prime ladder conjecture,” Integers , vol. 17, p. #A40, 2017. [Online]. Available: http://math.colgate.edu/~integers/r40/r40.pdf
[6]  N. Ramya, K. Rangarajan, and R. Sattanathan, “On  prime labeling of some classes of graphs,” International Journal of Computer Applications , vol. 44, no. 4, pp. 975–8887, 2012. [Online]. Available: https://research.ijcaonline.org/volume44/number4/pxc3878320.pdf

## 12
[7]  S. Meena and K. Vaithilingam, “Prime labeling of friendship graphs,” International Journal of Engineering Research & Technology (IJERT) , vol. 1, 2012, [Online]. Available: https://www.ijert.org/research/prime-labeling-of-friendship-graphs-IJERTV1IS10257.pdf
[8]  S. K. Vaidya and U. M. Prajapati, “Some new results on prime graphs,” Open Journal of Discrete Mathematics , vol. 02, no. 03, pp. 99–104, 2012, doi: 10.4236/ojdm.2012.23019.
[Online]. Available: https://www.scirp.org/pdf/OJDM20120300007_69764759.pdf
[9]  J. Asplund and N. B. Fox, “Minimum coprime labelings for operations on graphs,” Jul. 2017. [Online]. Available: http://arxiv.org/abs/1707.04471
[10]  J. Asplund and N. B. Fox, “Minimum coprime labelings of generalized Petersen and prism graphs,” Journal of Integer Sequences , vol. 24, no. 3, pp. 1–21, 2019. [Online]. Available: https://cs.uwaterloo.ca/journals/JIS/VOL24/Fox/fox11.pdf
[11]  C. Lee, “Minimum coprime graph labelings,” Journal of Integer Sequences , vol. 23, no. 11, pp. 1–15, 2020. [Online]. Available: https://cs.uwaterloo.ca/journals/JIS/VOL23/Lee/lee7.pdf
[12]  S-M. Lee, I. Wui, and J. Yeh, “On the amalgamation of prime graphs,” Bull. Malaysian Math. Soc , vol. 11, pp. 59–67, 1988.
[13]  H. Komarullah, Slamin, and K. Wijaya, “A minimum coprime number for amalgamation of wheel,” in Advances in Computer Science Research, volume 96, Proceedings of the International Conference on Mathematics, Geometry, Statistics, and Computation , 2022, pp. 53–57. https://doi.org/10.2991/acsr.k.220202.012
[14]  J. A. Gallian, “A dynamic survey of graph labeling,” The  Electronic  Journal of Combinatorics , p. 6, 2017. [Online]. Available: https://www.combinatorics.org/files/Surveys/ds6/ds6v20-2017.pdf
[15]  N. Hinding, D. Firmayas ari,  H.  Basir,  M.  Bača,  and  A.  Semaničová - Feňovčíková,  “On irregularity strength of diamond network,” AKCE International Journal of Graphs and Combinatorics , vol. 15, no. 3, pp. 291–297, Dec. 2018. https://doi.org/10.1016/j.akcej.2017.10.003
[16]  Sukirman, Teori Bilangan , 1st ed. Tangerang Selatan: Universitas Terbuka, 2016.