## Bilangan Kromatik Lokasi pada Graf Hasil Amalgamasi Sisi dari Graf Bintang dan Graf Lengkap
Fiqih Rahman Hartiansyah 1 , Darmaji 2
1 Institut Sains dan Teknologi Annuqayah, fiqih.math@gmail.com
2 Institut Teknologi Sepuluh Nopember Surabaya, darmaji@matematika.its.ac.id
DOI 10.31102/zeta.2023.8.2.66-70

## ABSTRACT
The locating coloring of graph extends the vertex coloring dan partition dimension of graph. The minimum number of locating coloring of graph G is called the locating chromatic number of graph G. In this paper will discuss the locating chromatic number of edge amalgamation graph of star graph with order m+1 and complete graph with order n. The method used to obtain the locating chromatic number of graph is to determine the upper dan lower bound. The results obtained are that the locating chromatic number of edge amalgamation graph of star graph with order m+1 and complete graph with order n is 𝑚𝑎𝑥{𝑚, 𝑛} for 𝑚 ≥ 3 and 𝑛 ≥ 4 . .
Keywords: locating chromatic number, edge amalgamation graph, star graph, complete graph

## ABSTRAK
Pewarnaan  lokasi  pada  graf  merupakan  pengembangan  dari  konsep  pewarnaan  simpul  dan dimensi  partisi  pada  graf.  Banyaknya  warna  minimum  pada  pewarnaan  lokasi  dari  graf  G  disebut bilangan  kromatik  lokasi  dari  graf  G.  Pada  penelitian  ini  dibahas  tentang  bilangan  kromatik lokasi pada graf hasil amalgamasi sisi dari graf bintang dengan order m+1 dan graf lengkap dengan order n. Metode  yang  digunakan  untuk  mendapatkan  bilangan  kromatik  lokasi  dari  graf  adalah  dengan menentukan batas atas dan batas bawah. Hasil yang diperoleh bahwa bilangan kromatik lokasi pada graf  hasil  amalgamasi sisi  dari  graf  bintang dengan order 𝑚 + 1 dan graf lengkap dengan  order 𝑛 adalah 𝑚𝑎𝑥{𝑚, 𝑛} untuk 𝑚 ≥ 3 dan 𝑛 ≥ 4 .
Kata Kunci : bilangan kromatik lokasi, graf hasil amalgamasi sisi, graf bintang, graf lengkap
1. PENDAHULUAN
Pewarnaan lokasi pada graf merupakan pengembangan  dari  konsep  pewarnaan  simpul  dan dimensi partisi pada graf. Kajian tentang pewarnaan lokasi pada graf merupakan kajian yang cukup baru di bidang teori graf. Konsep pewarnaan lokasi  yang pertama  kali  dikaji  oleh  Chartrand,  dkk.  (2002). Peneliti ini menentukan bilangan kromatik lokasi dari beberapa  kelas  graf,  diantaranya  graf  lintasan,  graf sikel, graf bintang ganda dan graf multipartit lengkap. Bilangan kromatik lokasi pada graf lintasan 𝑃 𝑛 adalah 3 untuk 𝑛 ≥ 3 . Pada graf sikel diperoleh 𝜒 𝐿 (𝐶 𝑛 ) = 3 untuk 𝑛 ganjil  dan 𝜒 𝐿 (𝐶 𝑛 ) = 4 untuk 𝑛 genap. Sedangkan  pada  graf  bintang  ganda  diperoleh 𝜒 𝐿 (𝑆 𝑎,𝑏 ) = 𝑏 + 1 untuk 1 ≤ 𝑎 ≤ 𝑏 dan 𝑏 ≥ 2 . Misalkan  graf  terhubung 𝐺 berorder 𝑛 ≥ 3 ,  maka 𝜒 𝐿 (𝐺) = 𝑛 jika  dan  hanya  jika  graf  multipartit lengkap. Sehingga bilangan kromatik lokasi pada graf lengkap 𝐾 𝑛 adalah 𝑛 .
Chartrand,  dkk.  (2003)  juga  mengkarakterisasi semua graf terhubung 𝐺 berorder 𝑛 dengan bilangan kromatik  lokasi 𝑛 − 1 dan 𝑛 − 2 .  Asmiati,  dkk.
(2011)  menentukan  bilangan  kromatik  lokasi  pada graf  hasil  amalgamasi  simpul  dari 𝑘 buah  graf bintang. Bilangan kromatik lokasi pada graf bintang 𝑆 𝑛 adalah 𝑛 + 1 .  Penulis  lain  juga  menentukan bilangan kromatik lokasi pada graf-graf hasil operasi, diantaranya  adalah  Baskoro  dan  Purwasih  (2012) menentukan bilangan kromatik lokasi pada graf hasil korona  dari  dua  graf,  Behtoei  dan  Anbarloei (2014) menentukan bilangan kromatik lokasi pada graf hasil join dari dua graf.
Beberapa  penulis,  diantaranya  Darmawahyuni dan  Narwen  (2016)  menentukan  bilangan  kromatik lokasi dari graf ulat, Silvia, dkk. (2018) menentukan bilangan  kromatik  lokasi  pada  graf  lobster 𝐿 𝑛,𝑚,1 dengan 𝑛 = 2,3,4 dan 𝑚 = 3 ,  Nur,  dkk.  (2020) menentukan  bilangan  kromatik  lokasi  untuk  graf pohon  pisang 𝐵 𝑛,𝑘 dan  Rahmatalia,  dkk.  (2022) menentukan  bilangan  kromatik  lokasi  graf  split lintasan.
Berdasarkan  uraian  di  atas,  maka  tujuan  dari penelitian  ini  adalah  untuk  mendapatkan  bilangan kromatik lokasi pada graf hasil amalgamasi sisi dari graf  bintang  dengan order 𝑚 + 1 dan  graf  lengkap dengan order 𝑛 .

## 2. TINJAUAN PUSTAKA
2.1 Terminologi Dasar Graf Graf,  dinotasikan  dengan 𝐺 = (𝑉, 𝐸) adalah pasangan  himpunan  berhingga (𝑉, 𝐸) dengan 𝑉(𝐺) adalah  himpunan  tak  kosong  dari  elemen  yang disebut  simpul  ( vertex )  dan 𝐸(𝐺) adalah  himpunan (boleh  kosong)  dengan  elemen  dari  pasangan  tak terurut (𝑢, 𝑣) dengan 𝑢, 𝑣 ∈ 𝑉(𝐺) dan 𝑢 ≠ 𝑣 ,  yang disebut sisi ( edge ). Untuk penyederhanaan penulisan, sisi 𝑒 = (𝑢, 𝑣) ∈ 𝐸(𝐺) dapat  ditulis 𝑒 = 𝑢𝑣 ∈ 𝐸(𝐺) dan graf 𝐺 = (𝑉, 𝐸) dapat ditulis 𝐺 . Banyak simpul
dari graf 𝐺 disebut order dari 𝐺 , dinotasikan dengan |𝑉(𝐺)| sedangkan banyak sisi dari graf 𝐺 disebut size dari 𝐺 ,  dinotasikan  dengan |𝐸(𝐺)| .  Jika  terdapat sebuah  sisi  antara 𝑢 dan 𝑣 ,  yaitu 𝑒 = 𝑢𝑣 ∈ 𝐸(𝐺) maka  simpul 𝑢 dikatakan  bertetangga  ( adjacent ) dengan simpul 𝑣 sedangkan sisi 𝑒 dikatakan melekat ( incident ) dengan simpul 𝑢 dan 𝑣 . Derajat  ( degree )  simpul 𝑣 ,  dinotasikan deg (𝑣) adalah  banyak  sisi  yang  melekat  pada  simpul 𝑣 . Simpul  dengan  derajat  nol  disebut  simpul  terisolasi ( isolated  vertex )  sedangkan  simpul  dengan  derajat satu  disebut  simpul  anting  ( pendant ).  Sisi  yang simpul ujungnya pada simpul yang sama disebut loop sedangkan  beberapa  sisi  berbeda  yang  mempunyai simpul ujung yang sama disebut sisi ganda ( multiple edge ).  Graf  yang  tidak  mempunyai loop dan  sisi ganda disebut graf sederhana ( simple graph ). Graf 𝐺 disebut terhubung ( connected ) jika setiap dua simpul sebarang berbeda terhubung.

## 2.2 Jenis-Jenis Graf
2.2.1 Graf Bintang (Star Graph)
Graf  bintang,  dinotasikan  dengan 𝑆 𝑛 untuk 𝑛 ≥ 3 adalah  graf  terhubung  sederhana  yang  satu simpulnya  berderajat 𝑛 sedangkan  simpul  yang lainnya  berderajat  satu. Order dan size dari  graf bintang adalah 𝑛 + 1 dan 𝑛 .

## 2.2.2 Graf Lengkap (Complete Graph)
Graf  lengkap,  dinotasikan  dengan 𝐾 𝑛 untuk 𝑛 ≥ 4 adalah  graf  terhubung  sederhana  yang  setiap simpulnya berderajat 𝑛 − 1 . Order dan size dari graf lengkap adalah 𝑛 dan 𝑛(𝑛 − 1) 2 ⁄ .

## 2.3 Amalgamasi Sisi
Misalkan 𝐺 1 dan 𝐺 2 adalah  dua  graf terhubung. Amalgamasi sisi dari graf 𝐺 1 dan graf 𝐺 2 dengan menggabungkan sisi 𝑒 ∈ 𝐸(𝐺 1 ) dan sisi 𝑓 ∈ 𝐸(𝐺 2 ) ,  dinotasikan  dengan 𝑎𝑚𝑎𝑙 𝑠 (𝐺 1 , 𝐺 2 ; 𝑒, 𝑓) adalah  graf  yang  diperoleh  dengan  menggabungkan sisi 𝑒 dari graf 𝐺 1 dan sisi 𝑓 dari graf 𝐺 2 menjadi satu sisi 𝑔 ,  dimana 𝑔 adalah  sisi  bersama  dari  graf  hasil 𝑎𝑚𝑎𝑙 𝑠 (𝐺 1 , 𝐺 2 ; 𝑒, 𝑓) .
2.4 Bilangan Kromatik Lokasi
2.4.1 Pewarnaan Simpul
Pewarnaan  simpul  dari 𝐺 adalah  pemberian warna pada setiap simpul di 𝐺 sedemikian sehingga tidak  terdapat  dua  simpul  bertetangga  mempunyai warna  yang  sama.  Bilangan  kromatik  dari 𝐺 , dinotasikan  dengan 𝜒(𝐺) adalah  banyaknya  warna minimum pada pewarnaan simpul dari 𝐺 .

## 2.4.2 Dimensi Partisi
Misalkan 𝐺 adalah  graf  terhubung  dan Π = {𝑆 1 , 𝑆 2 , ⋯ , 𝑆 𝑘 } adalah partisi dari 𝑉(𝐺) . Untuk setiap 𝑣 ∈ 𝑉(𝐺) , representasi dari 𝑣 terhadap Π didefinisikan sebagai 𝑘 -vektor : 𝑟(𝑣|Π) =
(𝑑(𝑣, 𝑆 1 ), 𝑑(𝑣, 𝑆 2 ), ⋯ , 𝑑(𝑣, 𝑆 𝑘 )) ,  dimana 𝑑(𝑣, 𝑆 𝑖 ) = min {𝑑(𝑣, 𝑥): 𝑥 ∈ 𝑆 𝑖 } untuk 1 ≤ 𝑖 ≤ 𝑘 .  Jika  setiap simpul  di 𝐺 mempunyai  representasi  yang  berbeda terhadap Π , maka Π disebut partisi pembeda dari 𝐺 . Dimensi  partisi  dari 𝐺 ,  dinotasikan  dengan 𝑝𝑑(𝐺) adalah  banyaknya  partisi  minimum  pada  partisi pembeda dari 𝐺 .

## 2.4.3 Pewarnaan Lokasi
Misalkan 𝑐 adalah  pewarnaan- 𝑘 simpul  dari graf  terhubung 𝐺 dan Π = {𝐶 1 , 𝐶 2 , ⋯ , 𝐶 𝑘 } adalah partisi  dari 𝑉(𝐺) ke  dalam  kelas-kelas  warna  yang dihasilkan. Untuk setiap 𝑣 ∈ 𝑉(𝐺) , kode warna dari 𝑣 terhadap Π didefinisikan sebagai 𝑘 -vektor: 𝑐 Π (𝑣) = (𝑑(𝑣, 𝐶 1 ), 𝑑(𝑣, 𝐶 2 ), ⋯ , 𝑑(𝑣, 𝐶 𝑘 )) , dimana 𝑑(𝑣, 𝐶 𝑖 ) = min {𝑑(𝑣, 𝑥): 𝑥 ∈ 𝐶 𝑖 } untuk 1 ≤ 𝑖 ≤ 𝑘 .  Jika  setiap simpul  di 𝐺 mempunyai  kode  warna  yang  berbeda terhadap Π , maka 𝑐 disebut pewarnaan lokasi dari 𝐺 . Bilangan kromatik lokasi dari 𝐺 , dinotasikan dengan 𝜒 𝐿 (𝐺) adalah  banyaknya  warna  minimum  pada pewarnaan  lokasi  dari 𝐺 .  Karena  setiap  pewarnaan lokasi merupakan pewarnaan maka 𝜒(𝐺) ≤ 𝜒 𝐿 (𝐺) .
Proposisi 2.1 Misalkan 𝐻 adalah subgraf dari graf 𝐺 . Maka 𝜒 𝐿 (𝐺) ≥ 𝜒 𝐿 (𝐻) . Bukti. Apapun  warna-warna  yang  digunakan pada simpul-simpul dari subgraf 𝐻 dalam pewarnaan lokasi  minimum  dari  graf 𝐺 juga  dapat  digunakan dalam  pewarnaan  lokasi  dari  subgraf 𝐻 dengan sendirinya. ∎

## 3. METODE PENELITIAN
Beberapa tahapan dilakukan sehingga  diperoleh teorema  terkait  bilangan  kromatik  lokasi  pada  graf hasil  amalgamasi  sisi  dari  graf  bintang  dan  graf lengkap sebagai berikut:
a. Mengkonstruksi  graf  hasil  amalgamasi  sisi  dari graf bintang dan graf lengkap.
b. Menentukan  pewarnaan  lokasi  pada  graf  hasil amalgamasi  sisi  dari  graf  bintang  dan  graf lengkap.
c. Menentukan  batas  atas  dari  bilangan  kromatik lokasi  diperoleh  dari  pewarnaan  lokasi  yang sesuai.
d. Menentukan batas bawah dari bilangan kromatik lokasi diperoleh dengan menggunakan proposisi dan teorema yang ada.

## 4. HASIL PENELITIAN
Teorema  4.1 Diberikan  graf bintang 𝑆 𝑚 dengan order 𝑚 + 1 dan  graf  lengkap 𝐾 𝑛 dengan order 𝑛 untuk 𝑚 ≥ 3 dan 𝑛 ≥ 4 .  Maka  bilangan  kromatik lokasi  pada  graf  hasil 𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒, 𝑓) adalah 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒, 𝑓)) = 𝑚𝑎𝑥{𝑚, 𝑛} .
Bukti. Ambil 𝑒 1 = 𝑓 1 ,  dimana  sisi 𝑒 1 ∈ 𝐸(𝑆 𝑚 ) dan sisi 𝑓 1 ∈ 𝐸(𝐾 𝑛 ) . Pandang tiga kasus berikut: Kasus 1: Untuk 𝑚 = 𝑛 .
Menentukan batas atas dari 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) untuk 𝑚 = 𝑛 .  Misalkan Π = {𝐶 1 , 𝐶 2 , ⋯ , 𝐶 𝑛 } adalah partisi dari 𝑉(𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) berdasarkan  pewarnaan simpul 𝑐 dengan: 𝐶 1 = {𝑤 1 } , 𝐶 2 = {𝑤 2 } ∪ {𝑢 3 } dan 𝐶 𝑖 = {𝑢 𝑖+1 , 𝑣 𝑖 } untuk 3 ≤ 𝑖 ≤ 𝑛 .
Kode  warna  dari  setiap  simpul  di  graf  hasil 𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 ) terhadap Π dapat dilihat pada 𝑛 kelas warna berikut:
i. Kelas warna 𝐶 1 : 𝑐 Π (𝑤 1 ) = (0,1, ⋯ ,1) . ii. Kelas  warna 𝐶 2 : 𝑐 Π (𝑤 2 ) = (1,0, ⋯ ,1) dan 𝑐 Π (𝑢 3 ) = (1,0, ⋯ ,2) . iii. Kelas  warna 𝐶 𝑖 : 𝑐 Π (𝑢 𝑖+1 ) = (1,2, ⋯ , ⋯ ) dan 𝑐 Π (𝑣 𝑖 ) = (1,1, ⋯ , ⋯ ) untuk 3 ≤ 𝑖 ≤ 𝑛 dengan  koordinat  ke- 𝑖 pada  setiap  kode warna adalah 0 .
Sehingga dapat dilihat bahwa setiap simpul di graf hasil 𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 ) mempunyai  kode  warna yang  berbeda  terhadap Π .  Jadi, 𝑐 adalah  pewarnaan lokasi  pada  graf  hasil 𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 ) dan 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) ≤ 𝑛 . Menentukan batas bawah dari 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) untuk 𝑚 = 𝑛 . Berdasarkan Gambar 1, di graf hasil 𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 ) terdapat subgraf yang isomorfis dengan graf bintang 𝑆 𝑚−1 dan graf lengkap 𝐾 𝑛 .  Sehingga  dengan  menggunakan  Proposisi  2.1 diperoleh 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) ≥ 𝜒 𝐿 (𝑆 𝑚−1 ) = 𝑚 atau 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) ≥ 𝜒 𝐿 (𝐾 𝑛 ) = 𝑛 . Karena 𝑚 = 𝑛 maka 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) ≥ 𝑛 . Karena 𝑛 ≤ 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) ≤ 𝑛 maka 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) = 𝑛 .
Gambar  1.  Pewarnaan  lokasi  pada  graf  hasil 𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 ) untuk 𝑚 = 𝑛 . Kasus 2: Untuk 𝑚 < 𝑛 . Menentukan batas atas dari 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) untuk 𝑚 < 𝑛 .  Misalkan Π = {𝐶 1 , 𝐶 2 , ⋯ , 𝐶 𝑛 } adalah
partisi dari
𝑉(𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) berdasarkan  pewarnaan simpul 𝑐 dengan:
𝐶 1 = {𝑤 1 } , 𝐶 2 = {𝑤 2 } ∪ {𝑢 3 } , 𝐶 𝑖 = {𝑢 𝑖+1 , 𝑣 𝑖 } untuk 3 ≤ 𝑖 ≤ 𝑚 dan 𝐶 𝑖 = {𝑣 𝑖 } untuk 𝑚 + 1 ≤ 𝑖 ≤ 𝑛 .
Kode  warna  dari  setiap  simpul  di  graf  hasil 𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 ) terhadap Π dapat dilihat pada 𝑛 kelas warna berikut:
i. Kelas warna 𝐶 1 : 𝑐 Π (𝑤 1 ) = (0,1, ⋯ ,1) .
ii.
Kelas  warna 𝐶 2 : 𝑐 Π (𝑤 2 ) = (1,0, ⋯ ,1) dan 𝑐 Π (𝑢 3 ) = (1,0, ⋯ ,2) . iii.
Kelas warna 𝐶 𝑖 : 𝑐 Π (𝑢 𝑖+1 ) = (1,2, ⋯ ,2) dan 𝑐 Π (𝑣 𝑖 ) = (1,1, ⋯ ,1) untuk 3 ≤ 𝑖 ≤ 𝑚 dengan  koordinat  ke- 𝑖 pada  setiap  kode warna adalah 0 . iv. Kelas  warna 𝐶 𝑖 : 𝑐 Π (𝑣 𝑖 ) = (1,1, ⋯ , ⋯ ) untuk 𝑚 + 1 ≤ 𝑖 ≤ 𝑛 dengan koordinat ke- 𝑖 pada setiap kode warna adalah 0 .
Sehingga dapat dilihat bahwa setiap simpul di graf hasil 𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 ) mempunyai  kode  warna yang  berbeda  terhadap Π .  Jadi, 𝑐 adalah  pewarnaan lokasi  pada  graf  hasil 𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 ) dan 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) ≤ 𝑛 . Menentukan batas bawah dari 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) untuk 𝑚 < 𝑛 . Berdasarkan Gambar 2, di graf hasil 𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 ) terdapat subgraf yang isomorfis dengan graf bintang 𝑆 𝑚−1 dan graf lengkap 𝐾 𝑛 .  Sehingga  dengan  menggunakan  Proposisi  2.1 diperoleh 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) ≥ 𝜒 𝐿 (𝑆 𝑚−1 ) = 𝑚 atau 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) ≥ 𝜒 𝐿 (𝐾 𝑛 ) = 𝑛 . Karena 𝑚 < 𝑛 maka 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) ≥ 𝑛 . Karena 𝑛 ≤ 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) ≤ 𝑛 maka 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) = 𝑛 .
Gambar  2.  Pewarnaan  lokasi  pada  graf  hasil 𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 ) untuk 𝑚 < 𝑛 . Kasus 3: Untuk 𝑚 > 𝑛 . Menentukan batas atas dari 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) untuk 𝑚 > 𝑛 .  Misalkan Π = {𝐶 1 , 𝐶 2 , ⋯ , 𝐶 𝑚 } adalah partisi dari 𝑉(𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) berdasarkan  pewarnaan simpul 𝑐 dengan:
𝐶 1 = {𝑤 1 } , 𝐶 2 = {𝑤 2 } ∪ {𝑢 3 } , 𝐶 𝑖 = {𝑢 𝑖+1 , 𝑣 𝑖 } untuk 3 ≤ 𝑖 ≤ 𝑛 dan 𝐶 𝑖 = {𝑣 𝑖 } untuk 𝑛 + 1 ≤ 𝑖 ≤ 𝑚 . Kode  warna  dari  setiap  simpul  di  graf  hasil 𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 ) terhadap Π dapat  dilihat  pada 𝑚 kelas warna berikut:
i. Kelas warna 𝐶 1 : 𝑐 Π (𝑤 1 ) = (0,1,1, ⋯ ,1) . ii. Kelas warna 𝐶 2 : 𝑐 Π (𝑤 2 ) = (1,0,1, ⋯ ,2) dan 𝑐 Π (𝑢 3 ) = (1,0,2, ⋯ ,2) . iii. Kelas  warna 𝐶 𝑖 : 𝑐 Π (𝑢 𝑖+1 ) = (1,2, ⋯ ,2,2) dan 𝑐 Π (𝑣 𝑖 ) = (1,1, ⋯ ,2,2) untuk 3 ≤ 𝑖 ≤ 𝑛 dengan  koordinat  ke- 𝑖 pada  setiap  kode warna adalah 0 .
iv. Kelas  warna 𝐶 𝑖 : 𝑐 Π (𝑣 𝑖 ) = (1,2,2,2, ⋯ ) untuk 𝑛 + 1 ≤ 𝑖 ≤ 𝑚 dengan koordinat ke- 𝑖 pada setiap kode warna adalah 0 . Sehingga dapat dilihat bahwa setiap simpul di graf hasil 𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 ) mempunyai  kode  warna yang  berbeda  terhadap Π .  Jadi, 𝑐 adalah  pewarnaan lokasi  pada  graf  hasil 𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 ) dan 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) ≤ 𝑚 . Menentukan batas bawah dari 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) untuk 𝑚 > 𝑛 . Berdasarkan Gambar 3, di graf hasil 𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 ) terdapat subgraf yang isomorfis dengan graf bintang 𝑆 𝑚−1 dan graf lengkap 𝐾 𝑛 .  Sehingga  dengan  menggunakan  Proposisi  2.1 diperoleh 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) ≥ 𝜒 𝐿 (𝑆 𝑚−1 ) = 𝑚 atau 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) ≥ 𝜒 𝐿 (𝐾 𝑛 ) = 𝑛 . Karena 𝑚 > 𝑛 maka 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) ≥ 𝑚 .
Karena 𝑚 ≤ 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) ≤ 𝑚
maka 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 )) = 𝑚 . Tanpa  mengurangi  keumuman,  ambil  sebarang 𝑒 = 𝑓 , dimana sisi 𝑒 ∈ 𝐸(𝑆 𝑚 ) dan sisi 𝑓 ∈ 𝐸(𝐾 𝑛 ) . Maka berlaku 𝜒 𝐿 (𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒, 𝑓)) = 𝑚𝑎𝑥{𝑚, 𝑛} .
∎
Gambar  3.  Pewarnaan  lokasi  pada  graf  hasil 𝑎𝑚𝑎𝑙 𝑠 (𝑆 𝑚 , 𝐾 𝑛 ; 𝑒 1 , 𝑓 1 ) untuk 𝑚 > 𝑛 .

## 5. KESIMPULAN
Hasil  dari  penelitian  ini  diperoleh  bilangan kromatik lokasi pada graf hasil amalgamasi sisi dari graf  bintang  dengan order 𝑚 + 1 dan  graf  lengkap dengan order 𝑛 adalah 𝑚𝑎𝑥{𝑚, 𝑛} untuk 𝑚 ≥ 3 dan 𝑛 ≥ 4 .

## DAFTAR PUSTAKA
Asmiati,  Assiyatun,  H.,  Baskoro,  E.T.  (2011) Locating-Chromatic  Number  of  Amalgamation  of Stars, ITB J. Sci. 43 A(1):1-8.
Amalia,  R.,  Firdausiyah,  Yulianto,  Tony.,  Faisol, Kuzairi. (2022) The Local Strong Metric Dimension in the Join of Graphs. Journal of Physics: Conference Series. 2157. 012004
Amalia,  R.,  Mufidah,  SA.,  Yulianto,  Tony.,  Faisol, Kuzairi. (2021) The complement metric dimension of particular tree. Journal of Physics: Conference Series.
1836. 012011.
Baskoro, E.T., Purwasih, I.A.  (2012) The  Locating- Chromatic  Number  for  Corona  Product  of  Graphs, Southeast-Asian J. of Sciences. 1(1):124-134.
Behtoei,  A.,  Anbarloei,  M.  (2014)  The  locating chromatic number of the join of graphs, Bull. Iranian Math. Soc. 40(6):1491-1504.
Chartrand, G., Erwin, D., Henning, M.A., Slater, P.J., Zhang, P. (2002) The locating-chromatic number of a graph, Bull. Inst. Combin. Appl. 36:89-101.
Chartrand, G., Erwin, D., Henning, M.A., Slater, P.J., Zhang,  P.  (2003)  Graphs  of  order  n  with  locating- chromatic  number  n-1,  Discrete  Mathematics. 269:65-79.
Chartrand,  G.,  Lesniak,  L.  (1996)  Graphs  & Digraphs, Chapman & Hall, London.
Chartrand,  G.,  Salehi,  E.,  Zhang,  P.  (2000)  The partition  dimension  of  a  graph,  Aequationes Mathematicae. 59:45-54.
Darmawahyuni,  A.,  Narwen.  (2016)  Bilangan Kromatik Lokasi Dari Graf Ulat, Jurnal Matematika UNAND. 5(1):1-6.
Gross,  J.L., Yellen,  J.  (2006)  Graph Theory  and  its Applications, Chapman & Hall, Francis.
Hartsfield,  N.,  Ringel  G.  (1990)  Pearls  in  Graph Theory, Academic Press, London.
Marsudi (2016) Teori Graf, UB Press, Malang.
Nur,  M.,  Welyyanti,  D.,  Narwen.  (2020)  Bilangan Kromatik  Lokasi  Untuk  Graf  Pohon  Pisang 𝑩 𝒏,𝒌 , Jurnal Matematika UNAND. 9(2):70-75.
Rahmatalia, S., Asmiati, Notiragayu. (2022) Bilangan Kromatik  Lokasi  Graf  Split  Lintasan,  Jurnal Matematika Integratif. 18(1):73-80.
Silvia,  M.,  Welyyanti,  D.,  Efendi.  (2018)  Bilangan Kromatik  Lokasi  Pada  Graf  Lobster 𝑳 𝒏,𝒎,𝟏 Dengan 𝒏 = 𝟐, 𝟑, 𝟒 Dan 𝒎 = 𝟑 , Jurnal Matematika UNAND. 7(3):94-103.
West,  D.B.  (2001)  Introduction  to  Graph  Theory, University of Illinois, Urbana.