Pelabelan Harmonis Pada Beberapa Kelas Graf Takhingga

Abstract

Pelabelan dalam teori graf merupakan metode pemberian label atau nilai pada titik atau sisi atau keduanya. Pelabelan harmonis adalah suatu pelabelan fungsi f:V(G)→Z, yang memetakan setiap titik dalam graf ke bilangan bulat sedemikian rupa sehingga label setiap titik adalah rata-rata dari label titik tetangganya, yaitu f(v)=1/(d(v)) ∑_(u∈N(v))▒〖f(u)〗. Pelabelan harmonis juga harus bersifat injektif, yaitu setiap titik diberi label yang unik, serta surjektif, yaitu setiap bilangan bulat yang dibutuhkan dapat digunakan, baik pada graf hingga maupun takhingga. Pada graf takhingga, aturan ini dapat dipastikan secara lokal di setiap lingkungan titik tanpa harus memperhitungkan seluruh struktur takhingga secara keseluruhan. Artikel ini membahas mengenai pelabelan harmonis pada graf takhingga. Keberadaan titik pendant merupakan syarat cukup bagi graf takhingga tidak memiliki pelabelan harmonis, namun bukan syarat perlu. Selain itu, graf G tetap memiliki pelabelan harmonis meskipun semua label digeser dengan konstanta atau diberi tanda negatif. Beberapa kelas graf yang dianalisis mencakup graf bintang B(n), pohon takhingga beraturan-k, produk kartesius graf, serta pengkuadratan graf.