Perpustakaan Digital ITB

Misalkan G adalah graf terhubung tak trivial dengan n titik dan k suatu bilangan bulat dengan 2 k n. Misalkan h 2 N, didefinisikan suatu pewarnaan-h c : E(G) ! f1; 2; :::; hg sehingga dua sisi yang bertetangga boleh memiliki warna yang sama. Suatu pohon T di G disebut pohon pelangi jika setiap sisi di T memiliki warna berbeda. Pewarnaan-h pelangi-k pada G adalah pewarnaan-h sisi pada G dengan setiap himpunan S dari k titik di G, terdapat pohon pelangi T sedemikian sehingga S V (T). Indeks pelangi-k untuk G, dinotasikan dengan rxk(G), adalah h terkecil sehingga terdapat pewarnaan-h pelangi-k pada G. Jarak Steiner d(S) dari himpunan S yang beranggotakan titik-titik di G adalah ukuran minimum dari pohon di G yang menghubungkan S. Pohon seperti itu disebut pohon Steiner. Diameter Steiner-k dari G, dinotasikan dengan sdiamk(G), adalah jarak Steiner maksimum dari S di antara seluruh himpunan S dengan k titik di G. Chartrand dkk. telah menunjukkan sdiamk(G) rxk(G) n ???? 1. Suatu pewarnaan-h sisi pada G disebut pewarnaan-h pelangi-k kuat jika setiap himpunan S dari k titik di G, terdapat pohon-S Steiner pelangi yang memuat S. Indeks pelangi-k kuat untuk G, dinotasikan dengan srxk(G), adalah h terkecil sehingga terdapat pewarnaan-h pelangi-k kuat pada G. Untuk t 2 N dengan t 2, misalkan fG1;G2; :::;Gtg adalah koleksi graf hingga terhubung sederhana dan setiap Gi memiliki sebuah titik tetap voi yang disebut titik terminal. Amalgamasi Amal(Gi; voi) adalah graf yang dibentuk dari gabungan graf Gi dengan meleburkan titik terminalnya. Jika untuk setiap i 2 f1; 2; :::; tg, Gi = G dan voi = v, Amal(Gi; voi) dinotasikan dengan Amal(G; v; t). Pada tesis ini ditentukan batas bawah dan batas atas indeks pelangi-3 (kuat) Amal(Gi; voi) untuk sebarang graf Gi. Selain itu juga ditentukan indeks pelangi-3 (kuat) untuk amalgamasi graf pohon, tangga, dan roda.