Perpustakaan Digital ITB

Misalkan H₁ dan H2 adalah dua graf sederhana dan berhingga. Suatu graf sederhana G = (V (G);E(G)) memuat selimut (H1;H2), dengan H1 dan H2 adalah dua subgraf di G, jika setiap sisi dari E(G) termuat pada minimal satu subgraf dari G yang isomorfik dengan grafH1 atauH2. Graf G dikatakan ajaib (H1;H2) jika terdapat fungsi bijektif f : V (G) S E(G) ! f1; 2; : : : ; jV (G)j + jE(G)jg dan bilangan asli k1 dan k2 sehingga untuk setiap subgraf H0 dari G yang isomorfik dengan graf H1, memiliki bobot subgraf w(H 0 ) = X v2V (H0 ) f(v) + X e2E(H0 ) f(e) = k1 dan setiap subgraf H00 dari G yang isomorfik dengan graf H2, memiliki bobot subgraf w(H 00 ) = X v2V (H00 ) f(v) + X e2E(H00 ) f(e) = k2: Selanjutnya, G dikatakan ajaib super (H1;H2), jika f(V (G)) = f1; 2; :::; jV (G)jg. Graf G korona H, dinotasikan dengan G H, adalah graf yang dibentuk dari G dan jV (G)j salinan H, sebut H1;H2; :::;HjV (G)j, kemudian setiap titik vi 2 V (G) dibuat bertetangga dengan semua titik di V (Hi) untuk i 2 f1; 2; ::; jV (G)jg. Dalam tesis ini ditentukan syarat perlu graf ajaib (Cn;K1;n) dan syarat perlu dan syarat cukup pohon korona lintasan T Pm yang ajaib super (Cn;K1;n) untuk n 3 dan m 2. Selain itu, ditentukan juga syarat perlu dan syarat cukup pohon tambah graf trivial T + K1 yang ajaib super (Cn;K1;n) untuk n 2 f3; 4g. Graf G tambah H, dinotasikan dengan G + H, adalah graf yang terbentuk dari graf G gabung H, kemudian setiap titik di G ke dibuat bertetangga dengan semua titik di H.