Kekuatan Sisi Refleksif pada Graf Hexagonal Snake dan Graf Caterpillar Korona Graf Path

Oleh :
Alvira Paris Damashinta - M0121008 - Fak. MIPA

Misal G = (V, E) adalah graf terhubung sederhana dengan himpunan vertex V(G) dan himpunan edge E(G). Pelabelan f dikatakan pelabelan-k refleksif tak teratur sisi pada G apabila bobot semua sisi berbeda, di mana setiap titiknya dapat diberi label bilangan bulat nonnegatif genap dari 0 hingga 2k_v dan setiap sisinya dapat diberi label bilangan bulat positif dari 1 hingga k_e. Jika uv adalah sisi, maka wt_f(uv) merupakan bobot sisi uv terhadap pelabelan f pada G, yaitu wt_f(uv) = f(u) + f(uv) + f(v). Nilai minimum label terbesar pada G adalah k dengan k = maks (k_e, 2k_v). Kekuatan sisi refleksif pada G, dinotasikan dengan res(G) adalah konstanta yang sama dengan k. Graf hexagonal snake yang dinotasikan dengan HS_n adalah graf yang diperoleh dari path u_1, u_2, ..., u_n dengan cycle yang terbentuk dari vertex yang bersebelahan dan connected, yaitu u_i: 1 ≤ i ≤ n, v_i, w_i: 1 ≤ i ≤ n-1, dan x_i: 1 ≤ i ≤ 2n-2. Kemudian, graf caterpillar korona graf path yang dinotasikan dengan Cp_n ⊙ P_m adalah graf hasil operasi korona antara graf caterpillar Cp_n dan graf path P_m. Penelitian ini bertujuan untuk menentukan kekuatan sisi refleksif res(G) dengan G adalah graf hexagonal snake HS_n dengan n ≥ 2 dan graf caterpillar korona graf path Cp_n ⊙ P_m dengan n ≥ 2 dan m ≥ 2. Metode yang digunakan dalam penelitian ini yaitu studi literatur yang bersumber dari buku dan artikel dalam jurnal mengenai pelabelan-k refleksif tak teratur sisi, dengan langkah-langkah: mengonstruksi graf beserta penamaan titik-titiknya, menentukan batas bawah res(G), menentukan batas atas res(G) dengan pelabelan sesuai batas bawah, menghitung bobot sisi sehingga setiap sisi memiliki bobot yang berbeda, menentukan pola umum label dan bobot, serta menentukan dan membuktikan nilai res(G) dari kedua graf tersebut. Dalam penelitian ini, diperoleh res(HS_n) dengan n ≥ 2 adalah 2(n-1), untuk 6n-6 ≡ 0 (mod 6). Kemudian, diperoleh res(Cp_n ⊙ P_m) dengan n ≥ 2 dan m ≥ 2 adalah ⌈(6nm-1)/3⌉, untuk 6nm-1 ≡ 5 (mod 6).