RAINBOW CONNECTION PADA GRAF AMALGAMASI TANGGA SEGITIGA DIPERUMUM HOMOGEN

Abstract

Untuk graf G terhubung dan tak trivial, dan k suatu bilangan bulat positif, misalkan c : E(G) → {1, 2, ..., k} suatu pewarnaan sisi di G, dimana sisi yang bertetangga boleh diberi warna yang sama. Suatu lintasan di G dikatakan lintasan rainbow jika tidak ada dua sisi di lintasan tersebut memiliki warna yang sama. Graf G dikatakan rainbow connected oleh pewarnaan c jika G memuat lintasan rainbow u − v untuk setiap titik u dan v di G. Dalam konteks ini, pewarnaan c disebut rainbow edge coloring. Jika c adalah rainbow edge coloring dengan k warna digunakan, maka c disebut rainbow k-coloring. Jika k adalah bilangan bulat positif yang minimum, maka k adalah bilangan rainbow connection dari graf G yang dinotasikan dengan rc(G) = k.

Untuk m ∈ N dan m ≥ 2, misalkan {G1, G2, . . . , Gm} adalah kumpulan hingga dari graf terhubung dan tak trivial, dan v0,i adalah sebuah titik graf Gi untuk 1 ≤ i ≤ m. Amalgamasi G1, G2, . . . , Gm yang dinotasikan dengan Amal{Gi, v0,i}m i=1 adalah graf yang berasal dari graf G1, G2, . . . , Gm dengan mengidentifikasi titiktitik v0,1, v0,2, . . . , v0,m sedemikian sehingga v0,1 = v0,2 = . . . = v0,m pada graf Amal{Gi, v0,i}m i=1. Graf Amal{T r4, v}m adalah graf amalgamasi m buah graf T r4, untuk m ≥ 2.

Pada makalah ini akan ditentukan bilangan rainbow connection pada graf amalgamasi tangga segitiga diperumum homogen Amal{T r4, v}m.

Diterima: Direvisi: Dipublikasikan :

Kata Kunci: bilangan rainbow connection, graf amalgamasi tangga segitiga diperumum homogen