Perpustakaan Digital ITB

Misalkan n, q, t ? N dan G = (V (G),E(G)) adalah graf sederhana dan berhingga yang memiliki orde |V (G)| = n dan ukuran |E(G)| = q. Misalkan f : V (G) ? E(G) ? {1, 2, . . . , n + q} adalah suatu pelabelan total pada G yang bersifat bijektif. Pelabelan f disebut pelabelan total sisi ajaib jika terdapat suatu konstanta k sehingga bobot setiap sisi e = uv di G, yaitu w(uv) = f(u)+f(v)+f(uv) = k. Dalam hal ini, k disebut konstanta ajaib. Sebaliknya, jika seluruh bobot sisi berbeda, maka f disebut sebagai pelabelan total sisi antiajaib. Pelabelan total sisi ajaib dapat diperluas dengan memandang subgraf dari G dalam perhitungan bobot. Misalkan {H1,H2, . . . ,Ht} adalah koleksi yang berisi t subgraf dari G, dan Hi isomorfik dengan suatu graf H, 1 ? i ? t. Graf G disebut memuat dekomposisi-H apabila setiap sisi di G termuat pada tepat satu subgraf di antara H1,H2, ...,Ht. Pelabelan f disebut pelabelan total H-ajaib dari G jika setiap 1 ? i ? t, bobot subgraf w(Hi) = P v?V (Hi) f(v) + P e?E(Hi) f(e) bernilai konstan. Sebaliknya, jika seluruh bobot subgraf berbeda, maka f disebut sebagai pelabelan total H-antiajaib. Selain dekomposisi suatu graf menjadi subgraf-subgraf yang saling isomorfik, di dalam literatur juga dikenal dekomposisi menjadi subgraf-subgraf yang tidak isomorfik. Misalkan q dan t memenuhi ????t+1 2 ? q < ????t+2 2 . Graf G disebut memuat dekomposisi subgraf terurut naik (ascending subgraf decomposition) atau ASD jika G dapat didekomposisi menjadi t subgraf H1,H2, . . . ,Ht tanpa titik terisolasi, dengan {E(H1), . . . ,E(Ht)} mempartisi E(G) sedemikian hingga Hi isomorfik ke suatu subgraf sejati dari Hi+1 untuk 1 ? i ? t ? 1. Graf yang memuat dekomposisi subgraf terurut naik disebut graf ASD dan barisan subgraf {H1,H2, . . . ,Ht} disebut barisan subgraf terurut naik. Termotivasi oleh pelabelan total H-(anti)ajaib, dalam disertasi ini diperkenalkan dan dikaji eksistensi pelabelan ajaib dan antiajaib pada suatu graf ASD. Misalkan G adalah graf ASD dengan himpunan subgraf {H1,H2, . . . ,Ht}, dan f adalah pelabelan total pada G. Apabila untuk setiap 1 ? i ? t diperoleh w(Hi) = k, maka f disebut pelabelan ASD-ajaib dari G dan G disebut sebagai graf ASD-ajaib. Dalam penelitian ini dikaji sifat umum yang dimiliki oleh graf ASD-ajaib, yaitu rata-rata bobot dari seluruh subgraf terbatas di atas oleh bobot terbesar yang dapat dicapai oleh subgraf terkecil. Fakta ini kemudian digunakan untuk melakukan karakterisasi graf bintang, graf lintasan, dan graf siklus yang memuat pelabelan ASD-ajaib. Di sisi lain, jika dengan pelabelan f diperoleh bahwa w(Hi) ?= w(Hj) untuk setiap i ?= j, maka f disebut pelabelan ASD-antiajaib dari G. Apabila seluruh bobot tersebut membentuk suatu barisan aritmetika dengan bobot terkecil a dan beda d, maka f disebut pelabelan (a, d)-ASD antiajaib. Lebih khusus, f adalah pelabelan ASD-antiajaib super atau (a, d)-ASD-antiajaib super jika f(V (G)) = {1, 2, . . . , n}. Penelitian mengenai pelabelan ASD-antiajaib (super) dalam disertasi ini dimulai dengan konstruksi pelabelan ASD-antiajaib (super) berdasarkan pelabelan total sisi (anti)ajaib (super). Pada konstruksi ini, didefinisikan suatu graf konektor yang digunakan sebagai alat untuk mengonstruksi keluarga graf ASD. Kemudian, diperoleh syarat cukup bagi graf konektor sehingga graf ASD yang telah dibangun memuat pelabelan ASD-antiajaib. Selain itu, didefinisikan pula dekomposisi bobot terurut naik (AWD) pada graf. AWD bersama pelabelan total sisi antiajaib digunakan sebagai alat untuk membuktikan bahwa graf bintang, graf lintasan, dan graf siklus memuat pelabelan ASD-antiajaib. Selain itu, dalam penelitian ini dilakukan pula konstruksi pelabelan ASD-antiajaib (super) berdasarkan pelabelan totalH-ajaib dari graf dengan barisan subgraf terurut naik yang memuat graf padanan atau graf siklus dengan orde tiga. Dengan berbagai hasil yang diperoleh, kami menduga bahwa semua graf dengan banyak sisi positif memiliki pelabelan ASD-antiajaib. Disertasi ini ditutup dengan konstruksi pelabelan (a, d)-ASD-antiajaib yang diperoleh dengan memanfaatkan multihimpunan (t, ?)-antiseimbang terurut naik. Misalkan ? ? N dan X adalah multihimpunan. X disebut multihimpunan (t, ?)-antiseimbang terurut naik jika X dapat dipartisi menjadi submultihimpunan X1,X2, . . . ,Xt dengan ketentuan bahwa untuk 1 ? i < j ? t ? 1 berlaku |Xi| < |Xj | dan P x?Xi+1 x ? P x?Xi x = ?. Kelas-kelas graf yang dikaji adalah graf bintang, lintasan, siklus, dan graf lengkap. Selain itu, dikaji pula pelabelan (a, d)-ASD-antiajaib pada graf hasil operasi, yaitu graf hasil gabungan saling lepas, graf hasil amalgamasi-titik, amalgamasi-sisi, amalgamasi-subgraf, graf rantai, graf rantai yang diperluas, dan graf hasil korona yang diperluas.