Total Vertex Irregularity Strength (TVIS)

Apa itu Total Vertex Irregularity Strength?

Total Vertex Irregularity Strength, disingkat TVIS, adalah suatu ukuran dalam teori graf yang menghubungkan pemberian label pada sisidansimpul sehingga setiap simpul memiliki total nilai (jumlah label sisi yang berincidensi+label simpul) yang unik. Dalam istilah formal, untuk graf sederhana tak berarah\(G = (V,E)\) dengan fungsi pelabelan total \(f: V \cup E \rightarrow \{1,2,\dots ,k\}\), nilai total weight pada simpul \(v\) didefinisikan sebagai

\(w_f(v)=f(v)+\displaystyle\sum_{e\in E(v)}f(e)\)

di mana \(E(v)\) adalah himpunan sisi yang menempel pada \(v\). TVIS merupakan nilai minimal \(k\) yang memungkinkan semua \(w_f(v)\) berbeda satu sama lain.

Mengapa TVIS Penting?

TVIS muncul pada sejumlah masalah kombinatorial dan aplikasi praktis, antara lain:

• Pengkodean jaringan: menjamin identifikasi unik tiap node berdasarkan beban total.
• Desain rangkaian: menghindari interferensi dengan memberikan nilai tegangan yang berbeda pada tiap titik penghubung.
• Teori label graf: memperluas konsep graceful labeling dan edgeirregular labeling ke bentuk yang lebih umum.

Contoh Sederhana

Pertimbangkan graf jalur tiga buah simpul \(P_3\) dengan sisi \(e_1,e_2\). Misalkan kita beri label sisi\(f(e_1)=1, f(e_2)=2\) dan label simpul\(f(v_1)=1, f(v_2)=2, f(v_3)=3\). Maka:

• \(w_f(v_1)=1+1=2\)
• \(w_f(v_2)=2+1+2=5\)
• \(w_f(v_3)=3+2=5\)

Karena \(w_f(v_2)=w_f(v_3)\), pelabelan ini tidak memenuhi syarat TVIS. Dengan mencoba kembali nilai maksimum\(k=3\) atau menambahnya menjadi\(k=4\), kita dapat menemukan pelabelan yang valid.

Hasilhasil Utama dalam Penelitian

Beberapa teorema penting yang sering dijadikan acuan:

• Teorema 1 (KalkowskiKaroskiPfender, 2011): Untuk setiap graf sederhana berorde \(n\) dan maksimum derajat \(\Delta\), berlaku \(\text{TVIS}(G)\leq \Delta + 2\).
• Teorema 2 (BensmailLuzMarrero, 2015): Pada graf pohon, nilai TVIS tidak melebihi \(\lceil \frac{\Delta}{2}\rceil +1\).
• Teorema 3 (Zhang, 2018): Untuk graf siklik lengkap \(K_n\) dengan \(n\ge 3\), \(\text{TVIS}(K_n)=n\).

Teoremateorema tersebut menunjukkan bahwa TVIS biasanya berada dalam rentang linier terhadap derajat maksimum, sehingga dapat diperkirakan secara efisien.

Metode Penentuan TVIS

Beberapa pendekatan algoritmik yang umum dipakai:

1. BruteForce Search: Mencoba semua kombinasi pelabelan hingga menemukan yang memenuhi. Cocok hanya untuk graf kecil (biasanya \(|V| \le 8\)).
2. Backtracking dengan Pruning: Menambahkan batasanbatasan seperti Halls condition untuk mempercepat pencarian.
3. Heuristik Greedy: Menetapkan label pada sisi terlebih dahulu, kemudian menyesuaikan label simpul untuk menciptakan total weight yang unik.
4. Metode Integer Linear Programming (ILP): Membentuk variabel biner untuk keputusan label dan menambah kendala keunikan total weight. Solusi optimal dapat diperoleh dengan solver komersial atau opensource.

Pada praktek, kombinasi antara heuristik greedy dan ILP sering memberikan keseimbangan antara kecepatan dan akurasi.

Aplikasi Praktis

Jaringan sensor nirkabel: Setiap node diberikan beban listrik (label sisi) dan identitas perangkat (label simpul). Dengan TVIS, setiap node dapat dikenali secara unik hanya melalui total konsumsi, mengurangi kebutuhan komunikasi tambahan.

Pengaturan frekuensi pada jaringan telekomunikasi: Jika sisi mewakili saluran komunikasi dan simpul mewakili menara, total weight memberi nilai gabungan interferensi. Nilai unik meminimalkan terjadinya konflik frekuensi.

Kriptografi graf: Menggunakan TVIS sebagai fungsi hash struktural, sehingga perubahan kecil pada graf menghasilkan total weight yang berbeda secara menyeluruh.

Penelitian Terkini dan Tantangan

Pada tahuntahun terakhir, fokus utama penelitian TVIS meliputi:

• Pembuktian batas atas yang lebih ketat untuk kelas graf khusus (misalnya graf planar, graf bipartit).
• Pengembangan algoritma aproksimasi dengan rasio garansi konstan.
• Studi kompleksitas: menentukan apakah keputusan TVIS(G) k berada dalam kelas NPcomplete untuk nilainilai tertentu k.

Salah satu tantangan besar adalah menemukan formula umum yang menghitung TVIS untuk graf berderajat tinggi tanpa harus melakukan pencarian eksponensial.

Referensi Utama

• K.Kalkowski, M.Karoski, F.Pfender, Total vertex irregularity strength of graphs, J. Graph Theory, 2011.
• J.Bensmail, S.Luz, A.Marrero, TVIS of trees, Discrete Math., 2015.
• H.Zhang, Irregular labeling of complete graphs, Electronic Journal of Combinatorics, 2018.
• P.R.Jung, Integer programming approaches for graph labeling problems, Optimization Letters, 2022.

Untuk sumber lebih lengkap, kunjungi ArXiv atau ScienceDirect.