Perpustakaan Digital ITB

Misalkan G dan H merupakan dua graf sederhana dan berhingga. Graf G disebut memiliki selimut-H jika setiap sisi di G termuat dalam suatu subgraf dari G yang isomorfik dengan H. Selanjutnya, suatu fungsi bijektif f dari himpunan titik G gabung himpunan sisi G, V (G) ? E(G), ke {1, 2, . . . , |V (G)| + |E(G)|} disebut pelabelan total f pada G. Misalkan G memiliki selimut-H. Pelabelan total f pada G disebut pelabelan H-ajaib jika terdapat suatu bilangan bulat positif k sehingga w(H?) = P v?V (H?) f(v) + P e?E(H?) f(e) = k untuk setiap subgraf H? dari G yang isomorfik dengan H. Dalam hal ini, nilai w(H?) disebut sebagai bobot subgraf dan graf G disebut H-ajaib. Lebih lanjut, graf G dan pelabelan f secara berurutan disebut graf H-ajaib super dan pelabelan H-ajaib super, jika f(V (G)) = {1, 2, . . . , |V (G)|}. Misalkan H1 dan H2 merupakan dua graf yang sederhana dan berhingga. Dalam pengerjaan pelabelan H-ajaib (super), dapat diperiksa bahwa terdapat graf dengan pelabelan total yang secara simultan adalah pelabelanH1-ajaib (super) danH2-ajaib (super). Di sisi lain, terdapat juga graf yang H1-ajaib (super) dan H2-ajaib (super), tetapi tidak memiliki suatu pelabelan total yang H1-ajaib (super) dan sekaligus H2- ajaib (super). Oleh karena itu, eksistensi pelabelan total yang secara simultan adalah pelabelan H1-ajaib (super) dan pelabelan H2-ajaib (super) menarik untuk dikaji. Dengan demikian, pada disertasi ini, diperkenalkan pelabelan (H1,H2)-sim-ajaib (super) pada graf. Konsep pelabelan ini juga dimotivasi dari pelabelan (anti) ajaib total (totally (anti)magic), yaitu pelabelan total yang secara simultan merupakan pelabelan total sisi (anti)ajaib dan pelabelan total titik (anti)ajaib.Misalkan graf G? secara simultan memiliki selimut-H1 dan selimut-H2. Pelabelan total f? pada G? disebut pelabelan (H1,H2)-sim-ajaib jika secara simultan f? merupakan pelabelan H1-ajaib dan pelabelan H2-ajaib. Graf G? ini kemudian disebut sebagai graf (H1,H2)-sim-ajaib. Lebih lanjut, graf G? dan pelabelan f? secara berurutan disebut (H1,H2)-ajaib super dan pelabelan (H1,H2)-sim-ajaib super, jika f?(V (G?)) = {1, 2, . . . , |V (G?)|}. Pada disertasi ini, ditentukan beberapa subgraf terlarang sebagai syarat perlu graf yang bersifat (K2,H)-sim-ajaib bila H suatu graf lintasan, graf bintang, atau graf siklus. Selain itu, ditentukan juga syarat cukup graf sisi-ajaib yang (K2,H)-sim-ajaib-super. Konstruksi pelabelan (H1,H2)-sim-ajaib super pada graf hasil operasi tambah dan hasil kali Cartesius juga diberikan. Selanjutnya, dapat diperiksa bahwa terdapat graf yang tidak memiliki selimut-H1 dan selimut-H2, tetapi setiap sisinya dapat termuat dalam subgraf yang isomorfik dengan H1 atau H2. Graf G?? yang memenuhi kondisi tersebut dikatakan memiliki selimut-(H1|H2). Termotivasi dari hal tersebut, pada disertasi ini, diperkenalkan juga pelabelan (H1|H2)-ajaib (super). Misalkan G?? memiliki selimut- (H1|H2). Pelabelan total f?? pada G?? disebut pelabelan (H1|H2)-ajaib jika terdapat dua bilangan bulat positif k1 dan k2 sehingga w(H?) = P v?V (H?) f??(v) + P e?E(H?) f??(e) = k1 untuk setiap subgraf H? dari G?? yang isomorfik dengan H1 dan w(H??) = P v?V (H??) f??(v) + P e?E(H??) f??(e) = k2 untuk setiap subgraf H?? dari G?? yang isomorfik dengan H2. Lebih lanjut, f?? disebut pelabelan (H1|H2)- ajaib super jika f??(V (G??)) = {1, 2, . . . , |V (G??)|}. Pada disertasi ini, ditentukan beberapa subgraf terlarang sebagai syarat perlu graf yang bersifat (Cm|Sn)-ajaib untuk 3 ? n < m. Diberikan juga karakterisasi graf mH1 ? nH2 yang bersifat (H1|H2)-ajaib super dengan H1 tidak memuat H2 sebagai subgraf dan sebaliknya untuk kasus |m?n| ? 1. Dari hasil tersebut, diperoleh karakterisasi graf kCm?lSn yang bersifat (Cm|Sn)-ajaib super untuk |k ? l| ? 1. Selain itu, diberikan juga konstruksi pelabelan (H1|H2)-ajaib super pada graf hasil kali berakar total, amalgasi subgraf, dan belenggu.