Salah satu permasalahan yang sering dihadapi dalam tata kota adalah menentukan titik atau tempat strategis, agar pelayanan terhadap masyarakat dapat berjalan dengan baik dan optimal. Makna optimal di sini adalah pembangunan tempat strategis ditentukan seminimal mungkin tetapi semua kepentingan terpenuhi dengan waktu, biaya dan tenaga yang juga minimum. Permasalahan seperti ini dapat diselesaikan dengan matematika, khususnya dengan teori graf, dengan terlebih dulu menyajikan peta daerah untuk tata kota tersebut dalam graf.

Graf didefinisikan sebagai himpunan berhingga tak kosong yang elemennya disebut titik, bersama dengan himpunan yang elemennya disebut garis yang merupakan pasangan tak terurut dari dua titik berbeda. Salah satu konsep dalam teori graf untuk menyelesaikan jenis permasalahan di atas adalah himpunan pembeda dominasi. Himpunan pembeda dominasi adalah himpunan titik pada graf yang mempunyai dua sifat.  Sifat yang pertama adalah setiap dua titik pada graf tersebut mempunyai representasi yang berbeda terhadap himpunan titik yang dimaksud dan yang kedua adalah setiap titik pada graf yang bukan anggota himpunan tersebut membentuk garis dengan minimal satu titik pada himpunan tersebut. Adapun yang dimaksud dengan representasi suatu titik terhadap suatu himpunan yang berkardinalitas  adalah pasangan berurutan  elemen yang berupa jarak antar suatu titik dengan setiap elemen pada himpunan tersebut.

Pada artikel ini dibahas konsep lanjutan dari  himpunan pembeda dominasi, yaitu himpunan pembeda lokal dominasi pada graf. Perbedaannya adalah pada dua titik yang membentuk garis  mempunyai representasi yang berbeda terhadap himpunan pembedanya. Himpunan pembeda lokal dominasi dengan kardinalitas minimum disebut dengan dimensi metrik lokal dominasi. Lebih lanjut, pada artikel ini himpunan pembeda lokal dominasi diterapkan pada graf hasil operasi comb. Secara umum graf hasil operasi comb dari graf  dan  dinotasikan . Untuk selanjutnya graf  disebut induk dan graf  disebut daun dari graf hasil operasi comb  Hasil utama penelitian ini disajikan dalam empat teorema.

Teorema pertama menyajikan dimensi metrik lokal dominasi graf hasil operasi comb , dimana  adalah graf bintang, yaitu graf yang garisnya hanya terbentuk dari satu titik tertentu yang membentuk garis dengan semua titik yang lain. Teorema kedua menyajikan dimensi metrik lokal dominasi graf hasil operasi comb , dimana  adalah graf lengkap, yaitu graf yang setiap dua titiknya membentuk garis. dan yang ketiga menyajikan dimensi metrik lokal dominasi graf hasil operasi comb , dimana  adalah graf bipartit lengkap, yaitu graf yang himpunan titiknya dapat dipartisi menjadi dua himpunan dan setiap titik pada himpunan pertama membentuk garis dengan setiap titik pada himpunan kedua. Hasil yang terakhir adalah untuk graf hasil operasi comb , dimana  adalah graf siklus, yaitu graf yang berbentuk siklus.  Dari keempat hasil menunjukkan bahwa dimensi metrik lokal dominasin graf hasil operasi comb berkaitan dengan perkalian antara banyaknya titik pada graf induknya dengan dimensi metrik lokal dominasi graf daunnya.

Hasil secara lebih detil beserta pembuktiannya dapat dilihat langsung pada artikel asli yang dipublikasikan pada jurnal IAENG International Journal of Computer Science, Volume 51, Issue 2, February 2024, Pages 115-120 yang dapat diakses melalui laman yang tertera di bawah ini.

Penulis: Dr. Liliek Susilowati, S.Si., M.Si.
Fakultas Sains dan Teknologi, Universitas Airlangga
Artikel lengkap dengan judul:

“The Local Resolving Dominating Set of Comb Product Graphs”

Dapat diakses melalui laman: https://www.iaeng.org/IJCS/issues_v51/issue_2/IJCS_51_2_06.pdf