Pelabelan Ketakteraturan Lokal Total Jarak Pada Keluarga Graf Pohon

Abstract

Teori graf adalah cabang matematika diskrit yang mempelajari hubungan antar objek melalui representasi titik dan sisi. Salah satu topik yang banyak diteliti dalam teori graf adalah pelabelan graf, yaitu pemberian label berupa bilangan bulat positif pada elemen-elemen graf dengan aturan tertentu. Chartrand memperkenalkan konsep irregular di mana label diberikan sedemikian sehingga setiap titik atau sisi memiliki bobot yang berbeda. Konsep ini ternyata berguna dalam berbagai situasi praktis, misalnya untuk menentukan frekuensi berbeda pada perangkat komunikasi supaya tidak saling mengganggu. Dari konsep dasar ini, mengembangkan pelabelan ketakteraturan total yang melibatkan label pada titik dan sisi sekaligus. Khusus pada graf pohon, yaitu graf terhubung yang tidak memiliki siklus, meneliti total vertex irregularity strength pada beberapa jenis graf seperti caterpillar, double star, broom, dan banana tree. Pendekatan lain pada graf yang dikenal distance irregular labelling yang hanya menggunakan label titik, dengan bobot titik dihitung dari jumlah label tetangga-tetangganya. Namun membuktikan bahwa graf pohon dengan 𝑛 ≥ tidak memiliki pelabelan distance irregular secara global, artinya tidak mungkin membuat bobot semua titik berbeda hanya dengan memberikan label pada titik. Penemuan ini mendorong beberapa peneliti untuk mengembangkan pendekatan lokal. Dalam pendekatan lokal, syarat ketakteraturan tidak perlu dipenuhi untuk semua titik, cukup untuk pasangan titik yang bertetangga saja. Kristiana pertama kali memperkenalkan pendekatan lokal ini pada masalah pewarnaan graf dan berhasil menunjukkan bahwa pendekatan lokal efektif untuk graf yang tidak bisa dilabeli secara global. Pendekatan yang sama kemudian diterapkan pada pelabelan graf. Kristiana & Alfarisi, mengembangkan local distance irregular labeling di mana untuk setiap 𝑢𝑣, bobot titik 𝑢 harus berbeda dengan bobot titik 𝑣. Dengan cara ini graf pohon yang sebelumnya tidak bisa dilabeli secara global ternyata bisa dilabeli dengan syarat pendekatan lokal. Hasil penelitiannya menentukan local distance irregularity strength yang dinotasikan 𝑑𝑖𝑠𝑙(𝐺) untuk berbagai graf seperti path, cycle, star, complete graph, tadpole, binary tree, dan complete bipartite.