Karakteristik Pelabelan Harmonis, Harmonis Ganjil dan Harmonis Genap

Abstract

Pelabelan harmonis pada graf G merupakan fungsi injektif f:V(G)→{0,1,2,3,… ,q - 1}sedemikian sehingga menghasilkan fungsi bijektif f^*: E(G)→{0,1,2,… ,q - 1} dengan f^* (uv)=f(u)+f(v)(mod q), untuk setiap uv ∈ E(G). Salah satu ciri yang menonjol daro graf harmonis yaitu selalu memuat lintasan tertutup. Selain itu, sifat dari pelabelan harmonis pada suatu graf tidaklah unik, sehingga akan terdapat fungsi pelabelan yang lain yang dapat melabeli graf tersebut secara harmonis. Misalkan f merupakan pelabelan harmonis pada graf G, maka fungsi g_f (u)=q-f(u)(mod q) dan fungsi g_f (u)=f(u)+k(mod q) untuk k∈{1,2,3,… ,q - 1} juga merupakan pelabelan harmonis pada graf G. Selain pelabelan harmonis terdapat pula pelabelan harmonis ganjil dan pelabelan harmonis genap. Pelabelan harmonis ganjil pada graf G merupakan fungsi injektif f yang memetakan setiap elemen di V(G) ke himpunan bilangan bulat non-negatif yang kurang dari 2q atau dapat kita tuliskan f: V(G)→{0,1,2,3,… ,2q-1} sedemikian sehingga terdapat fungsi f^* (uv)=f(u)+f(v) dengan f^* (uv)∈{1,3,5,… ,2q-1} untuk setiap uv ∈ E(G). Salah satu ciri dari graf harmonis ganjil yaitu tidak memuat cycle ganjil. Pelabelan harmonis ganjil pada suatu graf juga merupakan pelabelan yang tidak unik. Misalkan f merupakan pelabelan harmonis ganjil pada graf G, maka fungsi sepotong – sepotong g_f (v)=f(v)-1 untuk titik berlabel ganjil dan g_f (v)=f(v)+1 untuk titik berlabel genap juga merupakan pelabelan harmonis ganjil pada graf G. Sedangkan pelabelan harmonis genap yaitu merupakan fungsi injektif f:V(G)→{0,1,2,… ,2q} sedemikian sehingga terdapat fungsi bijektif f^*:E(G)→{0,2,4,… ,2q-2} dengan f^* (uv)=f(u)+f(v)(mod 2q) untuk setiap uv∈E(G). Misalkan f merupakan pelabelan harmonis genap pada graf G, maka fungsi g_f (u)=q-f(u)(mod q) dan fungsi g_f (u)=f(u)+q (mod 2q) juga merupakan pelabelan harmonis genap pada graf G