Perpustakaan Digital ITB

Misalkan G adalah suatu graf terhubung sederhana berorde n dan didefinisikan suatu pewarnaan sisi-h, c : E(G) ! f1; 2; : : : ; hg untuk suatu h 2 N dengan dua sisi yang bertetangga boleh memiliki warna yang sama. Suatu pohon T di G disebut pohon pelangi, jika tidak ada dua sisi di T yang memiliki warna sama. Suatu pewarnaan sisi ???? h pada G disebut pewarnaan sisi-h pelangi-k untuk suatu k 2 f2; 3; : : : ; ng, jika untuk setiap himpunan S V (G) dengan j S j= k, terdapat pohon pelangi di G yang memuat semua titik di S. Pohon pelangi seperti ini disebut pohon-S pelangi. Indeks pelangi-k graf G, dinotasikan dengan rxk(G), adalah bilangan bulat positif terkecil h sehingga terdapat suatu pewarnaan sisi-h pelangi-k pada G. Diberikan dua graf G1 = (V1;E1) dan G2 = (V2;E2). Hasil operasi penjumlahan G1 dan G2, dinotasikan dengan G1 + G2, adalah graf yang memiliki himpunan titik V (G1 + G2) = V (G1) [ V (G2) dan himpunan sisi E(G1 + G2) = E(G1) [ E(G2) [ fuv j u 2 V (G1); v 2 V (G2)g. Dalam tesis ini dikaji indeks pelangi-4 graf Cm + Pn untuk m 3 dan n 1.