GR Combinatorial Mathematics

Judul Penelitian : Pelabelan Refleksif Tak Reguler Sisi pada Beberapa Graf
Grup Riset : Combinatorial Mathematics
Tim Peneliti :
Dr. Dra. Diari Indriati, M.Si. (Ketua)
Prof. Drs. Tri Atmojo K., Ph.D.
Titin Sri Martini, S.Si., M.Kom.
Bowo Winarno, S.Si., M. Kom.
Dr. Putranto Hadi Utomo, M.Si.

Ringkasan Penelitian:

Graf G dapat dituliskan sebagai G(V,E) dengan V adalah himpunan titik yang berhingga dan tidak kosong, sedangkan E adalah himpunan sisi yang berhingga. Menurut Wallis, pelabelan suatu graf adalah pemetaan yang membawa elemen-elemen graf ke bilangan-bilangan bulat positif atau non-negatif. Jika domainnya himpunan titik dan sisi, pelabelan disebut pelabelan total. Pada penelitian ini dibahas pelabelan total dengan anggota E dipetakan ke himpunan bilangan bulat {1, 2, 3, …, k_e}, sedangkan anggota V dipetakan ke himpunan bilangan bulat genap {0, 2, 4, …, 2k_e}. Label sisi anggota E diartikan sebagai banyak sisi yang menghubungkan 2 titik, sedangkan label pada titik anggota V diartikan sebagai banyak loop pada titik tersebut. Jika bobot semua sisi berbeda, maka pelabelan disebut pelabelan refleksif tak reguler sisi (edge irregular reflexive labeling). Bobot sisi didefinisikan sebagai jumlahan label sisi dan label kedua titik yang insiden ke sisi tersebut. Pelabelan refleksif tak reguler sisi dengan minimal label terbesar untuk semua titik dan sisinya adalah k = maks{k_e, 2k_e}, disebut pelabelan-k refleksif tak reguler sisi (edge irregular reflexive k-labeling). Bilangan k disebut kekuatan sisi refleksif (reflexive edge strength) yang dinotasikan dengan res(G).

Pada penelitian ini diteliti pelabelan refleksif tak reguler sisi pada beberapa kelas graf yang belum pernah diteliti sebelumnya, antara lain pada beberapa klas graf sederhana . Metode yang dilakukan adalah dengan simulasi dan verifikasi algoritmik, yaitu dengan simulasi untuk mencari res(G) pada nilai n tertentu, kemudian dikembangkan untuk n sembarang, dengan n adalah banyak parameter pada G. Berikutnya  ditentukan nilai eksak untuk res(G) yang disajikan dalam bentuk formula algoritmik. Validasi hasil disajikan dalam bentuk teorema maupun lemma yang dibuktikan secara analitis, selanjutnya di presentasikan di forum-forum ilmiah ataupun dipublikasikan di jurnal bereputasi. Penelitian ini melibatkan beberapa mahasiswa.