Pelabelan Antimagic Jarak Terbukti pada Graf Herschel

Pada 2013, Nobuaki Kamachi dan Subramanian Arumugam memperkenalkan satu jenis pelabelan titik pada graf. Aturannya sederhana. Tiap titik diberi satu angka berbeda, lalu bobot sebuah titik dihitung dari jumlah angka seluruh tetangganya. Bila tidak ada dua titik yang bobotnya sama, pelabelan itu disebut antimagic jarak. Tiga belas tahun kemudian, giliran graf Herschel yang dibuktikan.

Pembuktian itu ditulis Peter John, Bonardo Lubis, dan Kiki Ariyanti Sugeng, matematikawan Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Indonesia. Artikel mereka, Distance Antimagic Labeling for Copies of Graph, terbit di Jurnal Matematika UNAND, Volume 15 Nomor 3 edisi Juli 2026, halaman 319–324. Naskahnya diterima 28 Februari 2026, direvisi 30 April, dan disetujui 7 Mei tahun yang sama.

2013: Dugaan yang Ditinggalkan Kamachi dan Arumugam

Kamachi dan Arumugam membuktikan empat hal pada tahun itu. Graf Petersen bersifat antimagic jarak. Begitu pula graf lingkaran, graf roda, dan graf lintasan. Empat pembuktian itu menjadi titik awal seluruh jalur riset yang menyusul sesudahnya. Hasil mereka terbit di Journal of Combinatorial Mathematics and Combinatorial Computing jilid ke-84.

Keduanya juga meninggalkan satu dugaan. Sebuah graf bersifat antimagic jarak jika dan hanya jika tidak ada dua titik berbeda yang himpunan tetangganya persis sama. Dugaan itu belum terbukti sampai hari ini. Seluruh kajian sesudahnya bergerak di sekitarnya, sebagian dengan menambah keluarga graf baru, sebagian lagi dengan menyusun alat pembuktian.

Dugaan itu berbunyi dalam dua arah sekaligus. Arah pertama menyatakan syarat itu perlu, arah kedua menyatakan syarat itu cukup. Sampai 2026, kepustakaan yang dikutip tim Universitas Indonesia belum memuat pembuktian maupun bantahan untuk dugaan tersebut.

Istilah salinan graf dipakai mengikuti definisi Stefan Burr, Paul Erdos, dan Joel Spencer pada 1975. Untuk sembarang bilangan bulat positif, salinan sebanyak n dari sebuah graf adalah gabungan saling lepas dari n graf yang semuanya serupa dengan graf itu. Definisi tersebut yang dipakai seluruh kajian berikutnya, termasuk naskah 2026.

2016 dan 2017: Alat Baru dari Handa dan Rekannya

Tiga tahun kemudian, Ashok Kumar Handa, Aloysius Godinho, dan Tarkeshwar Singh menambah dua keluarga graf. Graf Petersen diperumum terbukti antimagic jarak untuk orde lima ke atas. Graf Harary jenis tertentu terbukti untuk orde enam ke atas. Hasil itu terbit dalam prosiding Algorithms and Discrete Applied Mathematics jilid 9602.

Setahun sesudahnya, Handa dan rekan-rekannya kembali dengan hasil yang berbeda bentuk. Kali ini yang mereka susun bukan daftar graf, melainkan alat. Alat itu dipakai untuk membuktikan keberadaan pelabelan antimagic jarak pada operasi gabungan dan korona dua graf. Arumugam ikut sebagai penulis pada makalah kedua ini.

Perbedaan bentuk itu penting untuk jalur riset berikutnya. Daftar graf hanya menambah satu nama pada satu waktu. Alat bisa dipakai berulang untuk keluarga graf yang belum terpikirkan ketika alat itu disusun. Teorema gabungan dua graf inilah yang belakangan menopang seluruh pembuktian tim Universitas Indonesia.

Baca juga Penumpang Bandara Juanda Diramal Jitu Berkat Efek Lebaran

2021: Empat Keluarga Salinan Milik Simanjuntak

Pada 2021, Rinovia Simanjuntak bersama enam rekannya menerbitkan hasil di jurnal Symmetry. Gabungan dua graf lintasan terbukti antimagic jarak. Begitu pula salinan graf lintasan, salinan graf roda, salinan graf kipas, salinan graf persahabatan, dan salinan graf bintang. Enam keluarga graf sekaligus masuk daftar lewat satu artikel.

Di artikel yang sama mereka meninggalkan beberapa masalah terbuka. Satu di antaranya menjadi pintu masuk bagi tim Universitas Indonesia lima tahun kemudian. Masalah itu menyangkut graf yang tidak teratur, yaitu graf yang derajat titik-titiknya tidak seragam. Graf teratur sudah lebih dulu tertangani, graf tak teratur belum.

“Jika G adalah graf tak teratur yang tidak memuat dua titik dengan himpunan tetangga yang sama, tunjukkan bahwa salinan-salinannya bersifat antimagic jarak,” tulis Simanjuntak dan rekan-rekannya. Kalimat itu dikutip utuh oleh tim Universitas Indonesia di bagian pendahuluan naskah mereka, dan dijadikan sebagai rumusan masalah yang hendak dijawab sebagian.

2022: Graf Hasil Kali dan Korona Tritama

Setahun berikutnya, Simanjuntak kembali bersama Aholiab Tritama. Yang mereka buktikan kali ini graf hasil kali. Beberapa graf hasil kali kartesius masuk ke dalam daftar. Hasil itu terbit di jurnal yang sama dengan hasil setahun sebelumnya, yaitu Symmetry, pada jilid ke-14.

Keduanya juga membuktikan satu pernyataan bersyarat. Bila sebuah graf teratur bersifat antimagic jarak, maka hasil korona graf itu dengan graf berorde satu juga bersifat antimagic jarak. Pernyataan bersyarat semacam ini yang kemudian dipakai berulang oleh peneliti sesudahnya, termasuk pada pembuktian salinan graf teratur pada 2026.

2026: Sebelas Titik dan Delapan Belas Sisi

“Dalam makalah ini kami memberikan pembuktian parsial atas masalah yang diajukan dalam rujukan itu,” tulis John, Lubis, dan Sugeng. Pembuktian mereka dibagi dua. Bagian pertama menyangkut graf teratur secara umum. Bagian kedua menyangkut satu graf tak teratur yang dipilih sebagai contoh, yaitu graf Herschel.

Bagian pertama diselesaikan dengan induksi matematika, dimulai dari kasus dua salinan. Bila sebuah graf teratur berderajat r bersifat antimagic jarak, maka salinan sebanyak n dari graf itu juga bersifat antimagic jarak. Buktinya berpijak pada teorema Simanjuntak dan rekan-rekannya dari 2021, karena salinan sebanyak k dari graf berderajat r tetap berderajat r.

Bagian kedua memilih graf Herschel. Graf itu bipartit, berorde sebelas, dan bersisi delapan belas. Dalam kepustakaan yang dikutip tim Universitas Indonesia, yaitu survei Joseph Gallian dan buku Douglas West, graf Herschel adalah graf polihedra tak Hamilton yang paling kecil.

Pelabelannya lurus saja. Sebelas titik diberi angka satu sampai sebelas secara berurutan, tanpa pengaturan khusus apa pun. Bobot seluruh titik dihitung dari jumlah label tetangganya. Hasilnya berbeda satu sama lain, dan graf Herschel pun dinyatakan bersifat antimagic jarak tanpa perlu konstruksi tambahan.

Untuk salinan graf Herschel, tim itu menggeser angka. Titik ke-i pada salinan ke-j diberi angka f(vi) ditambah sebelas dikali j dikurang satu. Dengan begitu seluruh angka pada n salinan berjalan dari satu sampai sebelas kali n tanpa satu pun berulang. Label terkecilnya satu, label terbesarnya sebelas dikali jumlah salinan.

Bobot titiknya kemudian membentuk barisan aritmetika. Beda barisannya 44 untuk empat titik dan 33 untuk tujuh titik lainnya. Dua barisan berpotensi bertabrakan, yaitu barisan titik kedua dan barisan titik kesembilan. Sisa pembagian keduanya terhadap 33 ternyata berbeda, sehingga tabrakan itu tidak pernah terjadi.

Baca juga Prediksi Harga Saham BRI Model ARIMA-LSTM Bergalat 0,0297 Persen

Sesudah 2026: Graf Lintasan yang Tetap Menolak

Cara yang sama tidak bisa dipindahkan ke sembarang graf tak teratur. Tim Universitas Indonesia menunjukkannya lewat graf lintasan berorde enam. Graf itu sendiri bersifat antimagic jarak. Pelabelan berurutan satu sampai enam sudah cukup membuktikannya, karena bobot keenam titiknya keluar berbeda semua.

Persoalan muncul ketika graf itu disalin dua kali. Dengan konstruksi yang sama, titik berlabel empat dan titik berlabel tujuh sama-sama berbobot delapan. Dua bobot yang sama berarti pelabelan itu gugur seketika. Konstruksi yang berhasil pada graf teratur tidak bisa dipindahkan begitu saja ke graf tak teratur.

Gabungan dua graf lintasan sendiri sudah terbukti sejak 2021 oleh Simanjuntak dan rekan-rekannya. Yang gugur bukan pernyataannya, melainkan cara membuktikannya. Keduanya berdiri berdampingan di naskah 2026 itu sebagai pembatas cakupan pembuktian, sekaligus alasan mengapa graf Herschel ditangani secara tersendiri.

Batas kajiannya ditulis sendiri oleh tim Universitas Indonesia di bagian simpulan. Yang terbukti hanya graf teratur dan graf Herschel beserta salinannya. Salinan graf antimagic jarak yang tidak teratur secara umum diserahkan kepada riset berikutnya. Masalah terbuka Simanjuntak dan rekan-rekannya karena itu baru terjawab sebagian.

Naskah itu memuat dua hal kecil yang bisa diperiksa sendiri. Himpunan sisi graf lintasan berorde enam tertulis sebagai himpunan sisi graf berorde lima. Konstruksi yang dirujuk pada contoh itu disebut sebagai teorema, padahal di naskah yang sama nomor tersebut berstatus akibat. Keduanya tidak mengubah isi pembuktiannya.

Baca juga Titik Kuantum Grafena Geser Pendar Seng Oksida ke Hijau

Sampai Juli 2026, inilah posisi terakhir yang tercatat di jalur riset tersebut. Dugaan Kamachi dan Arumugam dari 2013 belum terbukti. Masalah terbuka Simanjuntak dan rekan-rekannya dari 2021 terjawab sebagian. Graf Herschel dan seluruh salinannya masuk daftar pada Juli 2026.