Pelabelan Total Sisi-Ajaib (Super)

Bab III Pelabelan Total Sisi-Ajaib (Super)

Pada bab ini diberikan sejarah singkat pelabelan graf serta konsep dasar dan hasilhasil yang sudah diketahui berkaitan dengan pelabelan total sisi-ajaib (super). Masalah terbuka dan konjektur terkini yang ada dalam area pelabelan ini juga disajikan. Di samping itu, pada bab ini disajikan hasil-hasil mengenai pelabelan total sisi-ajaib (super) yang telah kami dapatkan selama melakukan penelitian S3.

Pada bab ini dan selanjutnya diasumsikan bahwa G adalah graf berhingga yang mempunyai p titik dan q sisi.

III.1

Sejarah pelabelan graf

Konsep pelabelan graf mulai diperkenalkan pada tahun 1963 oleh Sedl´acˇek yang mendefinisikan pelabelan ajaib pada graf G sebagai suatu fungsi dari himpunan sisi graf G ke himpunan bilangan real sedemikian sehingga untuk setiap titik v di G jumlah semua label sisi yang menempel pada v adalah konstan. Konsep ini merupakan perumuman dari konsep bujur sangkar ajaib dimana bujur sangkar ajaib berukuran n × n bersesuaian dengan pelabelan ajaib dari graf bipartit lengkap Kn,n . Kemudian Stewart (1967) menyebut pelabelan tersebut sebagai pelabelan ajaib super jika himpunan label sisi yang digunakan adalah himpunan bilangan bulat berurutan.

Pada tahun 1967, Rosa memperkenalkan pelabelan graf jenis lain (β-valuation) yang merupakan suatu pelabelan titik. Pelabelan ini disebut juga sebagai pelabelan graceful (Golomb, 1972) dan istilah ini yang digunakan sampai sekarang. Konsep pelabelan graceful dikenalkan untuk memecahkan konjektur dari Ringel (1964) yang menyatakan bahwa setiap graf lengkap K2n+1 dapat didekomposisi menjadi 2n + 1 subgraf yang masing-masing isomorfik terhadap suatu graf pohon dengan n sisi. Secara formal, fungsi f dikatakan pelabelan graceful pada graf G dengan q sisi jika f merupakan fungsi satu-satu dari himpunan titik G ke {0, 1, 2, . . . , q} sedemikian sehingga jika setiap sisi xy diberi label |f (x) − f (y)|, maka himpunan semua label sisinya adalah {1, 2, 3, . . . , q}. Telah banyak laporan tentang karakterisasi graf yang mempunyai pelabelan graceful. Namun demikian, graf pohon belum 14

dapat ditentukan apakah senantiasa mempunyai pelabelan graceful atau tidak. Rosa (1970) memberikan konjektur bahwa setiap graf pohon mempunyai pelabelan graceful. Konjektur ini telah dibuktikan benar untuk beberapa kelas graf pohon misalnya lintasan, caterpillar, graf pohon yang memuat paling banyak 4 titik pendan, graf pohon dengan diameter 5 atau kurang, dan graf pohon dengan paling banyak 27 titik. Tetapi secara umum konjektur tersebut masih terbuka, bahkan masih terbuka untuk graf pohon yang mempunyai derajat maksimum 3. Selain itu, beberapa kelas graf yang lain juga telah dibuktikan mempunyai pelabelan graceful misalnya graf siklus, grid, prisma diperumum, dan bipartit lengkap (Gallian, 2007).

Pelabelan harmonius adalah pelabelan titik lain yang menarik untuk dikaji. Pelabelan harmonius pada graf G dengan q sisi didefinisikan sebagai suatu fungsi satusatu g dari himpunan titik G ke {0, 1, 2, . . . , q − 1} sedemikian sehingga jika setiap sisi uv diberi label g(u) + g(v) (mod q), maka himpunan semua label sisinya adalah {0, 1, 2, . . . , q −1}. Namun jika G suatu graf pohon, maka persyaratan satu-satu dari g tidak haruskan. Pelabelan ini diperkenalkan oleh Graham dan Sloane pada tahun 1980. Seperti pada pelabelan graceful, Graham dan Sloane (1980) mengemukakan konjektur bahwa semua graf pohon mempunyai pelabelan harmonius. Beberapa kelas graf telah dibuktikan mempunyai pelabelan harmonius misalnya graf caterpillar, pohon dengan maksimum banyaknya titik 26, bintang, grid, roda dan Petersen diperumum (Gallian, 2007). Namun konjektur di atas masih terbuka hingga kini.

Termotivasi oleh kedua jenis pelabelan tersebut, berbagai jenis pelabelan titik diperkenalkan dan dikaji. Gallian (2007) membaginya menjadi dua kelompok besar. Kelompok pertama adalah variasi dari pelabelan graceful dan kelompok kedua adalah variasi dari pelabelan harmonius. Pelabelan yang termasuk dalam kelompok pertama di antaranya adalah pelabelan-α, pelabelan graceful-like, pelabelan cordial, pelabelan k-equitable dan pelabelan hamming-graceful. Sedangkan pelabelan yang termasuk kelompok kedua di antaranya adalah pelabelan sequential, pelabelan elegant, dan pelabelan felicitous.

Di samping pelabelan titik, konsep pelabelan total juga diperkenalkan. Beberapa pelabelan yang termasuk tipe ini adalah pelabelan total sisi-ajaib, pelabelan total titik-ajaib, pelabelan total sisi-antiajaib (a, d), pelabelan total titik-antiajaib 15

(a, d). Fokus utama dalam disertasi ini adalah pada pelabelan total sisi-ajaib. Perkembangan pelabelan yang lain dapat dilihat pada makalah survey pelabelan graf (Gallian, 2007).

III.2

Pelabelan total sisi-ajaib

Pelabelan total sisi-ajaib pada graf G adalah suatu fungsi bijektif f : V (G) ∪ E(G) → {1, 2, 3, . . . , p + q} sedemikian hingga untuk suatu konstanta k berlaku f (x) + f (xy) + f (y) = k untuk setiap sisi xy ∈ E(G). Jika pelabelan dapat dikenakan pada G, maka k disebut konstanta ajaib dari f dan G disebut graf total sisi-ajaib atau dikatakan mempunyai pelabelan total sisi-ajaib.

Untuk mempersingkat, mulai saat ini, pelabelan total sisi-ajaib akan disebut sebagai pelabelan ajaib dan graf total sisi-ajaib akan disebut sebagai graf ajaib.

Untuk setiap pelabelan ajaib f pada graf G selalu terdapat pelabelan ajaib f 0 : V (G) ∪ E(G) → {1, 2, 3, . . . , p + q} yang didefinisikan dengan aturan f 0 (x) = p + q + 1 − f (x) untuk semua x ∈ V (G) ∪ E(G) seperti telah dibuktikan oleh Kotzig dan Rosa (1970). Pelabelan f 0 disebut sebagai pelabelan komplementer dari pelabelan f . Oleh Wallis et al. (2001), pelabelan ini disebut sebagai pelabelan dual dari pelabelan f . Istilah pelabelan dual akan digunakan pada disertasi ini. Lemma III.1 (Kotzig dan Rosa, 1970) Jika f adalah pelabelan ajaib pada graf G dengan konstanta ajaib k, maka pelabelan dual f 0 juga merupakan pelabelan ajaib pada G dengan konstanta ajaib k 0 = 3(p + q + 1) − k.

16

Suatu pelabelan ajaib pada graf siklus C4 dan pelabelan dualnya berturut-turut ditunjukkan pada Gambar III.1 (a) dan (b).

Gambar III.1. Pelabelan ajaib pada graf C4 dan pelabelan dualnya

Berikut ini disajikan survey perkembangan pada pelabelan ajaib. Graf lengkap Kn ajaib jika dan hanya jika n ∈ {1, 2, 3, 5, 6}, ini dibuktikan oleh Kotzig dan Rosa pada tahun 1972. Hasil ini diperoleh dengan menggunakan konsep himpunan tersebar rapi (well-spread set). Sebelumnya, pada tahun 1970, Kotzig dan Rosa membuktikan bahwa graf bipartit lengkap Km,n , graf siklus Cn dan graf caterpillar merupakan graf ajaib dan menunjukkan bahwa graf nK2 adalah graf ajaib jika dan hanya n ganjil. Mereka juga mengajukan konjektur berikut yang masih terbuka sampai saat ini. Konjektur III.1 (Kotzig dan Rosa, 1970) Semua graf pohon mempunyai pelabelan ajaib. Kebenaran konjektur tersebut telah diverifikasi oleh beberapa peneliti untuk beberapa kelas graf pohon di antaranya graf bintang (Wallis et al., 2000), graf kembang api, dan graf pohon pisang (banana tree graph) (Swaminathan dan Jeyanthi, 2000).

Beberapa hasil yang sudah dibuktikan oleh Kotzig dan Rosa dibuktikan kembali oleh Ringel dan Llado (1996). Hasil-hasil tersebut diantaranya adalah graf siklus dan graf caterpillar ditunjukkan sebagai graf ajaib. Pelabelan ajaib dari graf siklus juga dapat dilihat di (Golberg dan Slater, 1998) dan (Berkman et al., 2001). Syarat cukup untuk graf yang tidak ajaib juga diberikan oleh Ringel dan Llado (1996), seperti dinyatakan dalam lemma berikut.

17

Lemma III.2 (Ringel dan Llado, 1996) Jika G adalah suatu graf dengan q genap, setiap titik di G berderajat ganjil, dan p + q ≡ 2 (mod 4), maka G bukan merupakan graf ajaib. Bedasarkan Lemma III.2, graf roda Wn untuk n ≡ 3 (mod 4) dan graf Petersen diperumum P (n, m) untuk n ≡ 2 (mod 4) bukan merupakan graf ajaib.

Untuk n ≥ 3 ganjil dan m = 1 atau 2, graf Petersen diperumum P (n, m) merupakan graf ajaib sebagaimana telah dibuktikan oleh Ngurah dan Baskoro (2003). Graf buku Bn ∼ = K1,n × K2 merupakan graf ajaib untuk semua n (telah dibuktikan oleh Figueroa-Centeno et al. (2001)). Untuk n ≡ 0 dan 1 (mod 4), graf roda Wn (dengan n+1 titik) merupakan graf ajaib seperti telah dibuktikan Phillips et al. (2001). Sedangkan graf roda Wn merupakan graf ajaib untuk n ≡ 6 (mod 4), ini dibuktikan oleh Slamin et al. (2002). Fakta bahwa graf roda Wn merupakan graf ajaib untuk semua n kecuali untuk n ≡ 3 (mod 4) secara terpisah dibuktikan oleh Fukuci (2001). Pelabelan ajaib dari graf kipas Fn untuk semua n ≥ 2 diberikan oleh Figueroa-Centeno et al. (2001) dan Slamin et al. (2002).

Studi pelabelan ajaib pada kelas graf tak terhubung juga telah dilakukan. Pelabelan ajaib dari graf mP3 untuk m genap, m ≥ 4, diberikan oleh Baskoro dan Ngurah (2003). Hasil-hasil berikut telah dibuktikan oleh Figueroa-Centeno et al. (2005). Graf K1,m ∪ K1,n ajaib jika dan hanya jika n atau m genap, graf 2Pn ajaib untuk n ganjil, dan graf 2P4n ajaib untuk semua n. Selain itu, Kotzig (1971) menunjukkan bahwa: Teorema III.1 (Kotzig, 1971) Jika G suatu graf total sisi-ajaib, 3-colorable dan H∼ = mG dimana m ganjil, maka H adalah graf total sisi-ajaib. Adapun untuk m genap atau G bukan graf 3-colorable ketotalsisiajaiban mG (bila G total sisi-ajaib) masih merupakan persoalan terbuka.

Pelabelan ajaib juga telah dikaji oleh Avadayappan et al. (2000) dengan memperkenalkan istilah magic strength dari suatu graf. Magic strength dari suatu graf G didefinisikan sebagai konstanta ajaib terkecil dari semua pelabelan ajaib yang mungkin. Magic strength dari beberapa kelas graf seperti lintasan, bintang, siklus, dan graf bintang ganda telah mereka tentukan. 18

Baru-baru ini, pelabelan ajaib dikaji oleh Sugeng dan Miller (2005). Mereka mengkaji pelabelan ajaib dimana label titik atau label sisi berupa bilangan bulat positif berurutan. Hasil-hasil yang telah didapatkan oleh mereka antara lain seperti dinyatakan berikut ini. Jika G mempunyai pelabelan ajaib f dan f (V (G)) = {a + 1, a + 2, . . . , a + p}, a 6= 0 dan a 6= q, maka G adalah suatu graf tak terhubung. Jika G graf suatu graf terhubung, mempunyai pelabelan ajaib g dan g(E(G)) = {b + 1, b + 2, . . . , b + q}, dimana b ∈ {1, 2, . . . , p − 1}, maka G adalah suatu graf pohon.

Pada tahun 2001, Wallis memperkenalkan perluasan dari pelabelan ajaib yaitu injeksi sisi-ajaib (edge-magic injection) dari suatu graf. Injeksi sisi-ajaib pada suatu graf didefinisikan seperti pelabelan ajaib kecuali bahwa label yang digunakan sebarang bilangan bulat positif. Suatu injeksi sisi-ajaib disebut m-injeksi sisi-ajaib jika label terbesar yang digunakan adalah m. Tidak seperti pada pelabelan ajaib dimana tidak semua graf mempunyai suatu pelabelan ajaib, Wallis membuktikan bahwa setiap graf mempunyai suatu injeksi sisi-ajaib.

Variasi dari pelabelan ajaib juga telah dikaji. Combe, Nelson, dan Palmer pada tahun 2004 mengkaji pelabelan ajaib dari suatu graf hingga dimana label yang digunakan berupa unsur-unsur dari suatu grup komutatif sebarang dengan orde p + q. Kemudian, Combe dan Nelson (2006) mengkaji pelabelan ajaib dari suatu graf tak berhingga atas suatu grup komutatif dengan orde tak berhingga.

III.3

Pelabelan total sisi-ajaib super

Suatu graf ajaib G dengan pelabelan ajaib f disebut ajaib super jika f (V (G)) = {1, 2, 3, . . . , p}. semua graf pohon dengan maksimum banyaknya titik 17 mempunyai pelabelan ajaib super (Lee dan Shan, 2002). Graf pohon biner dengan sifat tertentu merupakan graf ajaib super (Fukuchi, 2000). Graf pohon pisang dan graf kembang api dengan sifat tertentu merupakan graf ajaib super (Swaminathan dan Jeyanthi, 2006). Setiap graf pohon dengan n titik adalah subgraf dari graf pohon yang ajaib super dengan 2n − 2 titik seperti telah dibuktikan oleh Llad´o (2006). Hasil tersebut diperbaharui oleh Ichishima et al. (2006) dengan membuktikan bahwa setiap graf

19

pohon dengan n titik adalah subgraf dari graf pohon yang ajaib super dengan 2n −3 titik.

Syarat perlu untuk suatu graf yang mempunyai pelabelan ajaib super diberikan oleh Enomoto et al. (1998) seperti dinyatakan dalam lemma berikut. Lemma III.3 (Enomoto et al., 1998) Jika G suatu graf ajaib super, maka q ≤ 2p − 3. Sebagai konsekuensi Lemma III.3, semua graf roda Wn , n ≥ 3 dan semua graf lengkap Kn , n ≥ 4, bukan merupakan graf ajaib. Pada tahun 1998, ketika istilah graf ajaib super untuk pertama kalinya diperkenalkan oleh Enomoto et al., mereka membuktikan bahwa graf siklus Cn merupakan graf ajaib super jika dan hanya jika n ganjil dan graf bipartit lengkap Km,n merupakan graf ajaib super jika dan hanya jika m = 1 atau n = 1. Di samping itu, mereka juga membuktikan bahwa semua graf pohon dengan masimum banyaknya titik 15 merupakan graf ajaib super. Berdasarkan fakta ini, Enomoto et al. mengemukakan konjektur yang serupa dengan Konjektur III.1. Konjektur III.2 (Enomoto et al., 1998) Semua graf pohon mempunyai pelabelan ajaib super. Konjektur III.2 telah dicoba untuk dipecahkan oleh banyak peneliti, tetapi hasilhasil yang didapatkan hanya berupa hasil-hasil parsial. Misalnya,b super. Lemma III.3 juga meng- akibatkan bahwa derajat minimum dari suatu graf ajaib super paling banyak 3. Kenyataan ini secara terpisah dibuktikan oleh Figueroa-Centeno et al. (2001) dan Cen (2001).

Syarat perlu dan syarat cukup untuk suatu graf yang ajaib super diberikan pada lemma berikut. Karena lemma berikut akan sering digunakan maka kami sajikan buktinya. Lemma III.4 (Figueroa-Centeno et al., 2001) Graf G adalah ajaib super jika dan hanya jika terdapat fungsi bijektif f : V (G) → {1, 2, 3, . . . , p} sehingga himpunan S = {f (u) + f (v)|uv ∈ E(G)} memuat q bilangan bulat berurutan. Dalam hal ini f dapat diperluas menjadi suatu pelabelan ajaib super dari G dengan konstanta ajaib k = p + q + min(S). 20

Bukti: Misalkan G adalah suatu graf ajaib super dan g adalah suatu pelabelan ajaib super pada G dengan konstanta ajaib k. Maka, S = {k − g(xy)|xy ∈ E(G)} = {k − (p + 1), k − (p + 2), . . . , k − (p + q)}. Ambil, f = g|V (G) . Sebaliknya, misalkan fungsi f seperti itu ada. Selanjutnya, misalkan xy ∈ E(G) sehingga f (x) + f (y) = min(S). f dapat diperluas ke suatu pelabelan ajaib super g dengan cara sebagai berikut. Definisikan g(x) = f (x) untuk setiap x ∈ V (G) dan g(xy) = p + q + min(S) − f (x) − f (y) untuk setiap xy ∈ E(G). g(E(G)) = {p + 1, p + 2, . . . , p + q}.

Jadi,

2

Berdasarkan Lemma III.4, untuk menyajikan graf ajaib super cukup ditampilkan pelabelan titiknya saja. Lemma berikut memberikan syarat cukup untuk graf yang tidak ajaib super. Lemma III.5 (Figueroa-Centeno et al., 2001) Jika G adalah suatu graf yang setiap titiknya berderajat genap dan banyaknya sisi di G adalah q ≡ 2 (mod 4), maka G tidak ajaib super. Sebagai akibat dari Lemma III.5, graf siklus Cn untuk n ≡ 2 (mod 4) dan graf pertemanan C3t dengan t ≡ 2 (mod 4) bukan merupakan graf ajaib super.

Lemma berikut ini dapat digunakan untuk menunjukkan bahwa graf reguler dengan jumlah sisi genap bukan merupakan graf ajaib super. Lemma III.6 (Figueroa-Centeno et al., 2001) Jika G adalah graf r-reguler (r > 0) dan ajaib super, maka q ganjil dan konstanta ajaib dari setiap pelabelan ajaib super dari G adalah 12 (4p + q + 3). Berdasarkan Lemma III.6, graf siklus Cn dan graf Petersen diperumum P (n, m) dengan n genap bukan merupakan graf ajaib super.

Seperti pada pelabelan ajaib, pelabelan dual juga didefinisikan untuk pelabelan ajaib super.

21

Lemma III.7 (Figueroa-Centeno et al., 2001) Jika f adalah pelabelan ajaib super pada graf G, maka fungsi f 0 : V (G) ∪ E(G) → {1, 2, 3, . . . , p + q} yang didefinisikan dengan   2p + q + 1 − f (x), jika x ∈ E(G), f 0 (x) =  p + 1 − f (x), jika x ∈ V (G). juga merupakan pelabelan ajaib super pada G. Pelabelan f 0 yang didefinisikan pada Lemma III.7 disebut pelabelan dual super dari pelabelan ajaib super f . Konstanta-ajaib dari f 0 adalah k 0 = 4p + q + 3 − k, dimana k adalah konstanta ajaib dari pelabelan ajaib super f . Hasil yang sama (Lemma III.7) secara terpisah juga didapatkan oleh Baskoro et al. (2005). Pelabelan ajaib super dan pelabelan dual super dari suatu graf ditunjukkan pada Gambar III.2.

Gambar III.2. Pelabelan ajaib super pada suatu graf dan pelabelan dualnya

Studi klasifikasi pelabelan ajaib super tidak hanya dilakukan pada kelas graf pohon, tetapi juga dilakukan pada kelas graf yang lain. Beberapa kelas graf terhubung telah dibuktikan ajaib super. Graf pertemanan C3t ajaib super jika dan hanya jika 3 ≤ t ≤ 5 dan t = 7 seperti telah dibuktikan oleh Slamin et al. (2002). Graf kipas Fn ajaib super jika dan hanya jika 1 ≤ n ≤ 6, graf tangga Ln ∼ = Pn × P2 ajaib super jika n ganjil, dan prisma diperumum Cm × Pn ajaib super jika m ganjil dan n ≥ 2 sebagaimana telah dibuktikan oleh Figueroa-Centeno et al. (2001). Mereka juga mengemukakan konjektur bahwa graf buku Bn ajaib super jika dan hanya jika n genap atau n ≡ 5 (mod 8).

Untuk k ≥ 1, pangkat k dari suatu graf G, dinotasikan dengan Gk , adalah suatu graf dengan V (Gk ) = V (G) dan uv ∈ E(Gk ) jika dan hanya jika 1 ≤ d(u, v) ≤ k. Graf Pnk ajaib super jika dan hanya jika k = 1 atau 2 dibuktikan oleh Figueroa-Centeno et al. (2001). Pelabelan ajaib super dari graf Petersen diperumum P (n, m) dapat dilihat di (Ngurah dan Baskoro, 2003) dan (Fukuchi, 2001). Pelabelan ajaib super dari 22

kelas graf terhubung yang lain dapat dilihat di (Rajashing et al.), (Swaminathan et al., 2006), dan (Lee dan Shan, 2002).

Beberapa graf tak terhubung juga sudah diketahui mempunyai pelabelan ajaib super. Beberapa kelas graf hutan linier merupakan graf ajaib super sebagaimana telah dibuktikan oleh Figueroa-Centeno et al. (2005). Graf tersebut antara lain adalah P3 ∪ nP2 untuk setiap n, P2 ∪ Pn untuk n ≥ 3, dan 2P4n untuk semua n. Pelabelan ajaib super beberapa kelas graf galaksi juga telah dikaji oleh mereka, misalnya K1,n ∪ K1,n+1 ajaib super jika dan hanya jika n ≥ 1, K1,m ∪ K1,n ajaib super jika m kelipatan dari n + 1, K1,2 ∪ K1,n ajaib super jika dan hanya jika n kelipatan 3, dan K1,3 ∪ K1,n ajaib super jika dan hanya jika n kelipatan 4. Berdasarkan fakta tersebut, mereka mengemukakan konjektur bahwa K1,m ∪ K1,n adalah ajaib super jika dan hanya jika m kelipatan dari n + 1 atau n kelipatan dari m + 1. Kebenaran konjektur tersebut telah dibuktikan Ivanˇco dan Luˇckaniˇcov´a (2002).

Pelabelan ajaib super juga dikaji oleh Avadayappan et al. (2001) dengan memperkenalkan istilah super magic strength dari suatu graf. Super magic strength dari suatu graf G didefinisikan sebagai konstanta ajaib terkecil dari semua pelabelan ajaib super yang mungkin. Super magic strength dari beberapa kelas graf, misalnya lintasan, bintang, siklus, dan graf bintang ganda, telah mereka tentukan.

Posisi dari pelabelan ajaib (super) diantara pelabelan yang lain dapat digambarkan sebagai berikut. Baca et al. (2001) membuktikan bahwa suatu graf yang mempunyai pelabelan ajaib juga mempunyai suatu pelabelan total sisi-antiajaib (a, d). Pelabelan total sisi-antiajaib (a, d) pada graf G dengan p titik dan q sisi adalah suatu fungsi satu-satu f : V (G) → {1, 2, 3, . . . , p + q} sedemikian sehingga {f (x) + f (xy) + f (y)|xy ∈ E(G)} = {a, a + d, a + 2d, . . . , a + (q − 1)d} untuk suatu bilangan bulat positif a dan d. Pelabelan ini diperkenalkan oleh Simanjuntak, Miller dan Bertault pada tahun 2000. Teorema III.2 (Baca et al., 2001) Misalkan G suatu graf yang mempunyai pelabelan ajaib dimana label sisinya berupa barisan aritmatika dengan beda d. Maka pernyataan berikut ekuivalen. 23

(i) G mempunyai pelabelan ajaib dengan konstanta ajaib k. (ii) G mempunyai pelabelan total sisi-antiajaib (k − (e − 1)d, 2d). Hubungan antara pelabelan ajaib super dengan pelabelan sequential, harmonius, pelabelan-α dan cordial telah dikaji oleh Figueroa-Centeno et al. (2001).

Pelabelan sequential pada graf G dengan q sisi adalah fungsi satu-satu f : V (G) → {0, 1, 2, . . . , q − 1} (label q disertakan jika G graf pohon) sedemikian sehingga jika f (uv) = f (u) + f (v), maka {f (uv)|uv ∈ E(G)} = {m, m + 1, m + 2, . . . , m + q − 1} untuk suatu bilangan bulat positif m. Graf G disebut graf sequential jika mempunyai suatu pelabelan sequential. Pelabelan ini pertama kali diperkenalkan oleh Grace pada tahun 1983. Teorema III.3 (Figueroa-Centeno et al. 2001) Misalkan G suatu graf dengan p titik dan q sisi dimana q ≥ p atau q = p − 1. Jika G ajaib super, maka G sequential dan harmonius. Rosa, pada tahun 1970, selain mengkaji pelabelan graceful juga mengkaji pelabelanα. Pelabelan graceful f pada graf G disebut pelabelan-α jika ada suatu konstanta positif k sehingga f (u) ≤ k < f (v) atau f (v) ≤ k < f (u) untuk setiap uv ∈ E(G). Teorema III.4 (Figueroa-Centeno et al. 2001) Misalkan G suatu graf pohon dengan V1 dan V2 adalah himpunan partisi dari V (G). Jika G mempunyai suatu pelabelan ajaib super sedemikian sehingga f (V1 ) = {1, 2, 3, . . . , |V1 |}, maka G mempunyai pelabelan-α. Pelabelan cordial pertama kali diperkenalkan oleh Cahit pada tahun 1987. Pelabelan cordial pada graf G adalah fungsi f : V (G) → {0, 1} sedemikian sehingga jika f (uv) = |f (u)−f (v)|, maka |vf (0)−vf (1)| ≤ 1 dan |ef (0)−ef (1)| ≤ 1, dimana vf (i) dan ef (i) berturut-turut menyatakan banyaknya titik v dan sisi e yang memenuhi f (v) = i dan f (e) = i untuk semua i ∈ {0, 1}. Suatu graf yang mempunyai pelabelan cordial disebut graf cordial. Teorema III.5 (Figueroa-Centeno et al. 2001) Jika G adalah graf ajaib super, maka G cordial. Perluasan lain dari pelabelan ajaib (super) juga telah diperkenalkan. Guti´errez dan Llad´o pada tahun 2005 memperkenalkan konsep selimut ajaib (magic covering) dari 24

suatu graf. Suatu graf G dikatakan mempunyai suatu selimut-H jika setiap sisi di G adalah sisi pada suatu subgraf (dari G) yang isomorfik dengan H. Misalkan G mempunyai suatu selimut-H. Pemetaan bijektif f : V (G) ∪ E(G) → {1, 2, 3, . . . , p + q} disebut pelabelan ajaib-H pada G jika terdapat konstanta positif k sedemikian hingga untuk setiap subgraf H 0 (dari G) yang isomorfik dengan H berlaku f (H 0 ) = P P v∈V (H 0 ) f (v) + e∈E(H 0 ) f (e) = k. Dalam hal ini, G disebut graf ajaib-H atau dikatakan mempunyai pelabelan ajaib-H. Jika f (V (G)) = {1, 2, 3, . . . , p}, maka f disebut pelabelan ajaib super-H pada G dan G disebut graf ajaib super-H. Pelabelan ajaib (super) adalah kasus khusus dari pelabelan ajaib (super)-H yaitu jika H adalah K2 .

Beberapa graf telah dibuktikan merupakan graf ajaib (super)-H atau bukan graf ajaib (super)-H untuk suatu H oleh Guti´errez dan Llad´o (2005). Misalnya, graf bintang K1,n merupakan graf ajaib super-K1,h untuk setiap 1 ≤ h ≤ n, graf lintasan Pn merupakan graf ajaib super-Ph untuk setiap 2 ≤ h ≤ n, graf lengkap Kn bukan merupakan graf ajaib-K1,h untuk setiap 2 ≤ h ≤ n−1, graf lengkap Kn bukan merupakan graf ajaib super-Ph untuk setiap 2 ≤ h ≤ n, dan graf bipartit lengkap Kn,n bukan merupakan graf ajaib super-K1,n untuk setiap n ≥ 2. Hasil-hasil lain dari pelabelan ini dapat dilihat di (Guti´errez dan Llad´o, 2005) dan (Llad´o dan Moragas, 2007).

III.4

Pelabelan ajaib (super) dari beberapa kelas graf

Konjektur Kotzig dan Rosa (Enomoto et al.) memberikan dorongan bagi banyak peneliti untuk mengkaji pelabelan ajaib (super) pada beberapa kelas graf pohon. Pada bab ini, kami mengkaji pelabelan ajaib super pada beberapa kelas graf pohon, yaitu pohon-seperti-lintasan (path-like tree), subdivisi dari graf bintang K1,3 dan graf lobster.

Di samping itu banyak peneliti mengkaji pelabelan ajaib (super) pada kelas graf yang lain, baik graf terhubung maupun graf tak terhubung, seperti sudah dinyatakan pada bab sebelumnya. Pada bab ini, kami juga mengkaji pelabelan ajaib pada kelas graf yang bukan graf pohon, yaitu graf rantai.

25

III.4.1

Pelabelan ajaib super pada graf pohon-seperti-lintasan

Istilah yang digunakan pada subbab ini mengikuti Barientos (2004). Misalkan Pt suatu graf lintasan yang mempunyai himpunan titik dan himpunan sisi berturutturut: V (Pt ) = {xi |1 ≤ i ≤ t} dan E(Pt ) = {xi xi+1 |1 ≤ i ≤ t − 1}. Pandang graf lintasan Pt sebagai subgraf dari graf grid (Pm × Pn ). Dalam grid, graf Pt dapat digambar sebagai graf yang terdiri dari subgraf-subgraf L1 , L2 , L3 . . . , Lk yang masing-masing merupakan segmen garis lurus terpanjang sehingga titik terakhir di Li adalah titik awal dari Li+1 . Sebagai contoh, Gambar III.3 menunjukkan graf P22 yang terdiri dari L1 ∼ = P2 , L2 ∼ = P4 , L3 ∼ = P2 , L4 ∼ = P4 , . . . dan seterusnya.

Gambar III.3. Graf P22 dipandang sebagai subgraf dari graf grid

Misalkan Li ∼ = P2 untuk suatu i dengan V (P2 ) = {u, v}, u ∈ Li−1 , v ∈ Li+1 . Misalkan u0 adalah titik (dapat lebih dari satu) di Li−1 yang berjarak satu (pada grid) ke titik v 0 di Li+1 . Transformasi elementer pada graf Pt adalah penggantian sisi Li dengan sebuah sisi baru u0 v 0 .

Graf pohon T dengan t titik disebut pohon-seperti-lintasan jika T dapat diperoleh dengan menerapkan sejumlah berhingga transformasi elementer pada Pt (yang dipandang sebagai subgraf dari graf grid ). Gambar III.4 menunjukkan dua buah pohon-seperti-lintasan yang didapatkan dari P22 pada Gambar III.3. Barientos (2004) menunjukkan bahwa setiap pohon-seperti-lintasan mempunyai pelabelan-α. Figueroa-Centeno et al. (2001) membuktikan bahwa setiap graf pohon yang mempunyai pelabelan-α adalah ajaib super. Dapat disimpulkan bahwa setiap pohon-seperti-lintasan merupakan graf ajaib super. Pada subbab ini, kami membuk26

Gambar III.4. Pohon-seperti-lintasan

tikan bahwa setiap pohon-seperti-lintasan adalah graf ajaib super melalui konstruksi langsung. Teorema III.6  Setiap pohon-seperti-lintasan adalah graf ajaib super. Bukti: Misalkan T adalah pohon-seperti-lintasan dengan n titik yang diperoleh dari Pn . Misalkan T0 = Pn , T1 , T2 , . . . , Tk = T adalah barisan graf pohon yang didapatkan dengan menerapkan serangkaian transformasi elementer kepada Pn . Selanjutnya, perhatikan pelabelan titik f pada Pn dari Kotzig dan Rosa (1970) berikut.   1 (i + 1), jika i ganjil, 2 f (xi ) =  b 1 (n + i + 1)c, jika i genap. 2 Berdasarkan Lemma III.4, f dapat diperluas menjadi suatu pelabelan ajaib super pada Pn dengan konstanta ajaib b 12 (5n + 3)c. Selanjutnya akan ditunjukkan bahwa f adalah suatu pelabelan ajaib super untuk setiap graf pohon pada barisan graf pohon tersebut. Misalkan f adalah pelabelan ajaib super pada Ti untuk suatu i ≥ 0. Akan ditunjukkan bahwa f juga merupakan pelabelan ajaib super dari Ti+1 . Misalkan Ti+1 adalah graf pohon yang didapatkan dari Ti dengan mengganti sisi uv dengan u0 v 0 . Melalui cara memperoleh Ti+1 dari Ti tampak bahwa label titik Ti+1 sama dengan label titik Ti . Selanjutnya per} hatikan partisi V1 , V2 dari V (Ti ). Jika n ganjil, misalkan f (V1 ) = {1, 2, 3, . . . , n+1 2 dan f (V2 ) = { n+1 + 1, n+1 + 2, n+1 + 3, . . . , n}. Jika n genap, misalkan f (V1 ) = 2 2 2 {1, 2, 3, . . . , n2 } dan f (V2 ) = { n2 + 1, n2 + 2, n2 + 3, . . . , n}. Perhatikan bahwa u dan v terletak pada himpunan titik yang berbeda dan demikian juga dengan u0 dan v 0 . 27

Jika u dan u0 (v dan v 0 ) terletak pada himpunan titik yang berbeda maka 1 1 f (u0 ) = f (v) − (d(u, u0 ) + 1) dan f (v 0 ) = f (u) + (d(u, u0 ) + 1). 2 2 Untuk kasus yang lain: Kasus 1: u ∈ V1 dan n genap, 1 1 f (u0 ) = f (v) − (n + d(u, u0 )) dan f (v 0 ) = f (u) + (n + d(u, u0 )), 2 2 Kasus 2: u ∈ V2 dan n genap, 1 1 f (u0 ) = f (v) + (n − 2 − d(u, u0 )) dan f (v 0 ) = f (u) − (n − 2 − d(u, u0 )), 2 2 Kasus 3: u ∈ V1 dan n ganjil, 1 1 f (u0 ) = f (v) − (n + 1 + d(u, u0 )) dan f (v 0 ) = f (u) + (n + 1 + d(u, u0 )), 2 2 Kasus 4: u ∈ V2 dan n ganjil, 1 1 f (u0 ) = f (v) + (n − 1 − d(u, u0 )) dan f (v 0 ) = f (u) − (n − 1 − d(u, u0 )), 2 2 dimana d(u, u0 ) adalah jarak antara u dan u0 di grid. Dapat diperiksa bahwa pada semua kasus berlaku f (u0 ) + f (v 0 ) = f (u) + f (v). Jadi f merupakan pelabelan titik yang dapat diperluas menjadi suatu pelabelan ajaib super pada Ti+1 .

2

Sebagai ilustrasi dari Teorema III.6, perhatikan Gambar III.5. Berdasarkan Lemma III.7 dan Teorema III.6, pohon-seperti-lintasan juga ajaib super dengan konstanta ajaib yang lain, seperti dinyatakan pada akibat berikut. Akibat III.1  Setiap pohon-seperti-lintasan ajaib super dengan konstanta ajaib b 21 (5n + 2)c.

28

Gambar III.5. Pelabelan titik pada P22 dan pohon-seperti-lintasan yang menunjukkan bahwa f (u0 ) + f (v 0 ) = f (u) + f (v)

29

Berdasarkan fakta tersebut dan sifat dualitas (Lemma III.1) didapatkan akibat berikut. Akibat III.2  Setiap pohon-seperti-lintasan merupakan graf ajaib dengan konstanta ajaib b 21 (7n − 2)c atau b 12 (7n − 1)c.

III.4.2

Pelabelan ajaib super pada graf subdivisi dari graf bintang K1,3

Untuk m, n, k ≥ 1, misalkan T (m, n, k) adalah graf yang didapatkan dengan cara menyisipkan berturut-turut m − 1, n − 1, dan k − 1 buah titik pada sisi pertama, kedua, dan ketiga dari suatu graf bintang K1,3 . Misalkan himpunan titik dan himpunan sisi dari graf T (m, n, k) didefinisikan sebagai berikut. V (T (m, n, k)) = {w} ∪ {xi |1 ≤ i ≤ m} ∪ {yi |1 ≤ i ≤ n} ∪ {zi |1 ≤ i ≤ k}, dan E(T (m, n, k)) = {wx1 , wy1 , wz1 } ∪ {xi xi+1 : 1 ≤ i ≤ m − 1} ∪{yi yi+1 : 1 ≤ i ≤ n − 1} ∪ {zi zi+1 : 1 ≤ i ≤ k − 1}. Graf T (m, n, k) terdiri dari m + n + k + 1 buah titik dan m + n + k buah sisi. Dari m + n + k + 1 buah titik tersebut, satu titik berderajat 3, tiga titik berderajat 1, dan titik yang lain berderajat 2. Graf T (4, 5, 7) ditunjukkan pada Gambar III.6.

Gambar III.6. Graf pohon T (4, 5, 7)

Lu (2001) menyebut graf T (m, n, k) sebagai graf three-path trees. Lu (2001 dan 2004) berturut-turut menunjukkan bahwa graf T (m, n, k) adalah ajaib super jika (a) m ≥ 1 dan n, k ganjil, (b) m, n ≥ 1 dan k = n + 1 atau k = n + 2. Pada subbab ini akan dibuktikan bahwa T (m, n, k) juga ajaib super jika m, n ≥ 1, dan k = n + 3 atau k = n + 4. 30

Misalkan T (m, n, k) mempunyai pelabelan ajaib dengan konstanta ajaib c dan t = m + n + k. Maka tc paling sedikit sama dengan jumlah yang didapatkan dengan memetakan label terkecil ke titik berderajat 3, t − 3 label terkecil berikutnya ke titik berderajat 2, dan 3 label terkecil berikutnya ke titik berderajat 1; dengan kata lain

tc ≥ 3 + 2

t−2 X

t+1 X

i+

i=2

2t+1 X

i+

i=t−1

i.

i=t+2

Batas atasnya dicapai dengan memetakan label terbesar ke titik berderajat 3, t − 3 label terbesar berikutnya ke titik berderajat 2, dan 3 label terbesar berikutnya ke titik yang lainnya, yaitu

tc ≤ 3(2t + 1) + 2

2t X i=t+4

i+

t+3 X i=t+1

i+

t X

i.

i=1

Jadi lemma berikut terbukti. Lemma III.8  Jika T (m, n, k) mempunyai pelabelan ajaib, maka konstanta ajaib c terletak pada interval berikut: 1 (5t2 2t

+ 3t + 6) ≤ c ≤

1 (7t2 2t

+ 9t − 6),

2

dengan t = m + n + k.

Dengan argumen yang sama lemma berikut juga dapat diperoleh. Lemma III.9  Jika T (m, n, k) mempunyai pelabelan ajaib super, maka konstanta ajaib c terletak pada interval berikut: 1 (5t2 2t

dengan t = m + n + k.

+ 3t + 6) ≤ c ≤

1 (5t2 2t

+ 11t − 6),

2

Dalam dua teorema berikut ditunjukkan bahwa T (m, n, k) untuk k = n + 3 dan k = n + 4 merupakan graf ajaib super. Untuk menunjukkan hal tersebut, misalkan α dan β adalah dua konstanta yang didefinisikan sebagai berikut:   0, jika n ≡ 2 (mod 4), α=  1, jika n ≡ 0, 1, 3 (mod 4),

31

dan

  d 1 (m − 4)e, jika n ≡ 0 (mod 2), 2 β=  d 1 (m − 2)e, jika n ≡ 1 (mod 2). 2

Teorema III.7  Untuk semua bilangan bulat m, n ≥ 1, T (m, n, n+3) mempunyai pelabelan ajaib super. Bukti: Definisikan pelabelan titik f : V (T (m, n, n + 3)) → {1, 2, 3, . . . , m + 2n + 4} sebagai berikut.    m + n + 3,       d m e − 12 (i − 1),   2 f (u) = m + n + 3 − 12 i,      d m2 e + 1 − α + 12 (i + 1),      m + n + 3 + 1 i, 2

jika u = w, jika u = xi untuk i ≡ 1 (mod 2), jika u = xi untuk i ≡ 0 (mod 2), jika u = yi untuk i ≡ 1 (mod 2), jika u = yi untuk i ≡ 0 (mod 2).

Titik-titik yang lain diberi label sebagai berikut. Kasus 1, n ≡ 0 mod 4,    d m2 e + n + 1 − 21 (i − 1),       d m e + n + 3 − 21 (i − 1),   2 f (zi ) = m + 2n + 4 − 12 i,      m + 2n + 6 − 21 i,      m + 3 n + 4, 2

untuk i ≡ 1 (mod 4), untuk i ≡ 3 (mod 4), untuk i ≡ 2 (mod 4), i 6= n + 2, untuk i ≡ 0 (mod 4), untuk i = n + 2.

Kasus 2, n ≡ 1 mod 4,    d m2 e + n + 1 − 12 (i − 1),      d m e + n + 3 − 1 (i − 1), 2 2 f (zi ) = 1   m + 2n + 4 − 2 i,      m + 2n + 6 − 1 i, 2

untuk i ≡ 1 (mod 4), untuk i ≡ 3 (mod 4), untuk i ≡ 2 (mod 4), untuk i ≡ 0 (mod 4).

Kasus 3, n ≡ 2 mod 4,    d m e + 1, untuk i = 1,   2 f (zi ) = d m2 e + n + 3 − 12 (i − 1), untuk i ≡ 1 (mod 2), i 6= 1,     m + 2n + 5 − 1 i, untuk i ≡ 0 (mod 2). 2

32

Kasus 4, n ≡ 3 mod 4,

f (zi ) =

                                      

d m2 e + n + 1 − 12 (i − 1), untuk i ≡ 1 (mod 4), i 6= n + 2, d m2 e + n + 3 − 12 (i − 1), untuk i ≡ 3 (mod 4), m + 2n + 4 − 12 i,

untuk i ≡ 2 (mod 4), i 6= n − 1,

m + 2n + 6 − 12 i,

untuk i ≡ 0 (mod 4), i 6= n + 1,

m + 5 + 21 (3n + 1),

untuk i = n − 1,

m + 3 + 21 (3n + 1),

untuk i = n + 1,

d m2 e + d n2 e + 1,

untuk i = n + 2,

m + 4 + 12 (3n + 1),

untuk i = n + 3.

Terhadap pelabelan titik f , jumlah label dua titik yang bertetangga dapat dinyatakan sebagai berikut.

f (w) + f (x1 ) = m + d f (w) + f (y1 ) = m + d

m e + n + 3, 2

m e + n + 5 − α, 2

  m + d m e + n + 4, jika n ≡ 2 (mod 4), 2 f (w) + f (z1 ) =  m + d m e + 2n + 4, jika n ≡ 0, 1, 3 (mod 4), 2 {f (xi ) + f (xi+1 ) : 1 ≤ i ≤ m − 1} = {d m2 e + n + 4, d m2 e + n + 5, . . . , m + d m2 e + n + 2}, {f (yi ) + f (yi+1 ) : 1 ≤ i ≤ n − 1} = {m + d m2 e + n + 6 − α, m + d m2 e + n + 7 − α, . . . , m + d m2 e + 2n + 4 − α}, {f (zi ) + f (zi+1 ) : 1 ≤ i ≤ n + 2} = {m + d m2 e + 2n + 5, m + d m2 e + 2n + 6, . . . , m + d m2 e + 3n + 6}.
Jadi himpunan S = {f (v) + f (w)|vw ∈ E T (m, n, n + 3) } memuat bilangan bulat yang berurutan dengan maks(S) = m + d m2 e + 3n + 6. Berdasarkan Lemma III.4, f dapat diperluas menjadi suatu pelabelan ajaib super dari T (m, n, n + 3) dengan konstanta ajaib c = 2m + d m2 e + 5n + 11.

2

Pelabelan titik dari graf T (4, 6, 9) yang ajaib super dengan konstanta ajaib 51 ditunjukkan pada Gambar III.7.

33

Gambar III.7. Pelabelan titik dari T (4, 6, 9).

Teorema III.8  Untuk semua bilangan bulat m, n ≥ 1, graf T (m, n, n + 4) mempunyai pelabelan ajaib super. Bukti: Misalkan g adalah pelabelan titik pada T (m, n, n + 4) yang didefinisikan sebagai berikut. Kasus 1, n ≡ 0 mod 2, g(u) = f (u), untuk u = w, xi , dan yi , dimana f adalah pelabelan titik yang didefinisikan dalam Teorema III.7 dengan α = 1. Subkasus 1.1, n ≡ 0 mod 4,    d m2 e + n + 1 − 21 (i − 1),      d m e + n + 3 − 1 (i − 1), 2 2 g(zi ) =   m + 2n + 5 − 12 i,      m + 2n + 7 − 1 i, 2

untuk i ≡ 1 (mod 4), untuk i ≡ 3 (mod 4), untuk i ≡ 2 (mod 4), untuk i ≡ 0 (mod 4).

Subkasus 1.2, n ≡ 2 mod 4,    d m2 e + n + 1 − 12 (i − 1),       d m2 e + n + 3 − 12 (i − 1),       m + 2n + 5 − 12 i,      m + 2n + 7 − 1 i, 2 g(zi ) = 3   m + 6 + 2 n,       m + 4 + 23 n,       d m+n e + 1,  2     m + 5 + 3 n, 2

untuk i ≡ 1 (mod 4), i 6= n + 3, untuk i ≡ 3 (mod 4), untuk i ≡ 2 (mod 4), i 6= n, n + 4, untuk i ≡ 0 (mod 4), i 6= n + 2 untuk i = n, untuk i = n + 2, untuk i = n + 3, untuk i = n + 4.

34

Kasus 2, n ≡ 1 mod 2,    m + n + 4,       d m e − 12 (i − 1),   2 g(u) = m + n + 4 − 12 i,     d m e + 2 + 1 (i − 1),   2 2     m + n + 4 + 1 i, 2

jika u = w, jika u = xi untuk i ≡ 1 (mod 2), jika u = xi untuk i ≡ 0 (mod 2), jika u = yi untuk i ≡ 1 (mod 2), jika u = yi untuk i ≡ 0 (mod 2).

   d m e + 1, untuk i = 1,   2 g(zi ) = d m2 e + n + 4 − 12 (i − 1), untuk i ≡ 1 (mod 2), i 6= 1,     m + 2n + 6 − 1 i, untuk i ≡ 0 (mod 2). 2 Terhadap pelabelan titik g, jumlah label dari dua titik yang bertetangga dapat dinyatakan dengan formula berikut. Kasus 1, n ≡ 0 mod 2, g(w) + g(x1 ) = m + d

m e + n + 3, 2

m e + n + 4, 2 m g(w) + g(z1 ) = m + d e + 2n + 4, 2 g(w) + g(y1 ) = m + d

{g(xi ) + g(xi+1 )|1 ≤ i ≤ m − 1} = {d m2 e + n + 4, d m2 e + n + 5, . . . , m + d m2 e + n + 2}, {g(yi ) + g(yi+1 )|1 ≤ i ≤ n − 1} = {m + d m2 e + n + 5, m + d m2 e + n + 6, . . . , m + d m2 e + 2n + 3}, {g(zi ) + g(zi+1 )|1 ≤ i ≤ n + 3} = {m + d m2 e + 2n + 5, m + d m2 e + 2n + 6, . . . , m + d m2 e + 3n + 7}. Kasus 2, n ≡ 1 mod 2, g(w) + g(x1 ) = m + d

m e + n + 4, 2

m e + n + 6, 2 m g(w) + g(z1 ) = m + d e + n + 5, 2

g(w) + g(y1 ) = m + d

35

{g(xi ) + g(xi+1 )|1 ≤ i ≤ m − 1} = {d m2 e + n + 5, d m2 e + n + 6, . . . , m + d m2 e + n + 3}, {g(yi ) + g(yi+1 )|1 ≤ i ≤ n − 1} = {m + d m2 e + n + 7, m + d m2 e + n + 8, . . . , m + d m2 e + 2n + 5}, {g(zi ) + g(zi+1 )|1 ≤ i ≤ n + 3} = {m + d m2 e + 2n + 6, m + d m2 e + 2n + 7, . . . , m + d m2 e + 3n + 8}. Jadi S = {g(v) + g(w)|vw ∈ E(T (m, n, n + 4))} memuat bilangan bulat berurutan dengan maks(S) = m + 3n + 9 + β. Berdasarkan Lemma III.4, g dapat diperluas menjadi suatu pelabelan ajaib super dari graf T (m, n, n + 4) dengan konstanta ajaib 2m + 5n + 15 + β.

2

Sebagai ilustrasi, pelabelan titik dari graf T (3, 6, 10) yang ajaib super dengan konstanta ajaib 51 ditunjukkan pada Gambar III.8.

Gambar III.8. Pelabelan titik dari T (3, 6, 10)

Berdasarkan Lemma III.7, T (m, n, n + 3) dan T (m, n, n + 4) juga mempunyai pelabelan ajaib super dengan konstanta ajaib yang lain, seperti dinyatakan pada dua akibat berikut. Akibat III.3  Untuk semua bilangan bulat m, n ≥ 1, T (m, n, n + 3) mempunyai pelabelan ajaib super dengan konstanta ajaib 3m + 5n + 10 − d 21 (m − 2)e.

2

Akibat III.4  Untuk semua bilangan bulat m, n ≥ 1, T (m, n, n + 4) mempunyai pelabelan ajaib super dengan konstanta ajaib 3m + 5n + 12 − β.

2

Berdasarkan sifat pelabelan dual (Lemma III.1) dan Teorema III.7 dan III.8, serta Akibat III.3 dan III.4, didapatkan hasil berikut. Akibat III.5  Untuk semua bilangan bulat m, n ≥ 1, T (m, n, n + 3) mempunyai pelabelan ajaib dengan konstanta ajaib 4m + 7n + 12 − d 21 (m − 2)e atau 3m + 7n + 14 − d 21 (m − 2)e.

2

36

Akibat III.6  Untuk semua bilangan bulat m, n ≥ 1, T (m, n, n + 4) mempunyai pelabelan ajaib dengan konstanta ajaib 4m + 7n + 15 − β atau 3m + 7n + 18 − β. 2 Hasil-hasil di atas menunjukkan bahwa untuk k = n+3 dan k = n+4, graf T (m, n, k) merupakan graf ajaib super. Kami belum dapat menunjukkan bahwa T (m, n, k) merupakan graf ajaib super untuk semua nilai k. Kami juga telah membuktikan bahwa T (m, n, n+3) dan T (m, n, n+4) merupakan graf ajaib (super) untuk beberapa nilai konstanta ajaib c, belum untuk semua nilai c yang mungkin. Berikut adalah masalah terbuka yang belum tercakup dalam hasil-hasil yang sudah didapatkan. Masalah Terbuka III.1 Carilah suatu pelabelan ajaib (super) dari T (m, n, k) untuk semua nilai m, n, dan k yang mungkin. Masalah Terbuka III.2 Carilah suatu pelabelan ajaib (super) dari T (m, n, n + 3) dan T (m, n, n + 4) untuk nilai konstanta ajaib c yang lain.

III.4.3

Pelabelan ajaib super pada graf lobster

Pada subbab ini, kami mengkaji pelabelan ajaib super dari kelas graf lobster yaitu graf kembang api dan graf lobster yang mempunyai struktur khusus (lihat Gambar III.10).

Misalkan G1 , G2 , G3 , . . . , Gn adalah graf bintang yang saling lepas dan ui adalah sebuah titik pendan di Gi , 1 ≤ i ≤ n. Graf pohon yang memuat G1 , G2 , G3 , . . . , Gn dan sebuah lintasan yang menghubungkan u1 , u2 , u3 , . . . , un disebut graf kembang api. Graf ini pertama kali diperkenalkan oleh Chen, Li, dan Yeh pada tahun 1997. Graf kembang api yang memuat graf bintang K1,m1 +1 , K1,m2 +1 , . . . , K1,mn +1 dinotasikan dengan F C(m1 , m2 , . . . , mn ).

Misalkan himpunan titik dan himpunan sisi dari F C(m1 , m2 , . . . , mn ) didefinisikan sebagai berikut. V (F C(m1 , m2 , . . . , mn )) = {ui , ui,i |1 ≤ i ≤ n} ∪ {uji,i |1 ≤ i ≤ n, 1 ≤ j ≤ mi },

37

dan E(F C(m1 , m2 , . . . , mn )) = {ui ui+1 |1 ≤ i ≤ n − 1} ∪ {ui ui,i |1 ≤ i ≤ n} ∪ {ui,i uji,i |1 ≤ i ≤ n, 1 ≤ j ≤ mi }. Jika mi = m untuk setiap 1 ≤ i ≤ n, graf kembang api F C(m1 , m2 , . . . , mn ) merupakan graf ajaib super seperti telah dibuktikan oleh Swaminathan dan Jeyanthi (2006). Pada subbab ini akan dibuktikan bahwa graf kembang api F C(m1 , m2 , . . . , mn ) juga merupakan graf ajaib super untuk kasus m1 ≤ m2 ≤ m3 ≤ . . . ≤ mn .

Untuk membuktikan hal tersebut, misalkan konstanta α didefinisikan sebagai berikut.

α=

 

n−1 , 2

jika n ganjil,



n−2 , 2

jika n genap.

Teorema III.9  Jika m1 ≤ m2 ≤ m3 ≤ . . . ≤ mn , maka F C(m1 , m2 , . . . , mn ) merupakan graf ajaib super. Bukti: Perhatikan pelabelan titik f : V (F C(m1 , m2 , . . . , mn )) → {1, 2, 3, . . . , p}, P dimana p = 2n + ni=1 mi , yang didefinisikan sebagai berikut.  i−1  m +i+P 2 m , jika i ganjil 1 2h h=1 f (ui ) = i−2 P P  n+i+ α m 2 2h+1 + h=1 m2h+1 , jika i genap. h=0 Titik yang berderajat mi + 1, 1 ≤ i ≤ n, diberi label sebagai berikut.  P i−1  n + i + Pα m 2 + 2h+1 h=1 m2h , jika i ganjil, h=0 f (ui,i ) = i−2  i+P 2 m jika i genap. 2h+1 , h=0 Semua titik pendan diberi label sesuai dengan formula berikut.    j,    P i−3  2   i + j − 1 +  h=0 m2h+1 ,   i−3   i+j+P 2 m 2h+1 , h=0 f (x) = P α   n + j + 2 + h=0 m2h+1 ,        − 1,      ,

jika x = uj1,1 , 1 ≤ j ≤ m1 , jika x = uji,i , i ≥ 3 ganjil, dan 1 ≤ j ≤ γ, jika x = uji,i , i ≥ 3 ganjil, dan 1 + γ ≤ j ≤ mi , jika x = uj2,2 , 1 ≤ j ≤ m2 , jika x = uji,i , i ≥ 4 genap, dan 1 ≤ j ≤ δ, jika x = uji,i , i ≥ 4 genap, dan 1 + δ ≤ j ≤ mi ,

38

P i−1 P i−3 P i−2 P i−2 2 2 2 2 dengan γ = m − m , δ = m − 2h 2h+1 2h+1 h=1 h=1 h=1 h=1 m2h , and  = P P i−2 2 n + i + j + αh=0 m2h+1 + h=1 m2h .

Terhadap pelabelan f jumlah label dua titik yang bertetangga dapat dinyatakan dengan formula berikut.

f (ui ) + f (ui+1 ) = n + m1 + 2i + 1 +

α X

m2h+1 +

h=0

i X

mh , 1 ≤ i ≤ n − 1.

h=2

 P i−1  n + m + 2i + Pα m 2 1 2h+1 + 2 h=1 m2h , jika i ganjil, h=0 f (ui ) + f (ui,i ) = i−2 P 2  n + m + 2i + Pα m 1 2h+1 + 2 h=1 m2h , jika i genap. h=0 f (u1,1 ) +

f (uj1,1 )

=n+1+j+

α X

m2h+1 , 1 ≤ j ≤ m1 ,

h=0

untuk i ≥ 3 ganjil,  Pi−1  n + 2i + j − 1 + Pα m 2h+1 + h=1 mh , 1 ≤ j ≤ γ, h=0 j f (ui,i ) + f (ui,i ) = P P i−1  n + 2i + j + α m γ + 1 ≤ j ≤ mi . 2h+1 + h=1 mh , h=0

f (u2,2 ) +

f (uj2,2 )

= n + m1 + 4 + j +

α X

m2h+1 , 1 ≤ j ≤ m2 ,

h=0

untuk i ≥ 4 genap,  Pi−1  n + 2i + j − 1 + Pα m 2h+1 + h=1 mh , 1 ≤ j ≤ δ, h=0 j f (ui,i ) + f (ui,i ) = P P i−1  n + 2i + j + α m δ + 1 ≤ j ≤ mi . 2h+1 + h=1 mh , h=0 Perhatikan bahwa untuk i = 1, 2, 3, . . . , n, P Ai = {f (ui,i ) + f (uji,i ) | 1 ≤ j ≤ mi } ∪ {f (ui ) + f (ui,i )} = {n + 2i + αh=0 m2h+1 + Pi−1 Pα Pi−1 Pα h=1 mh , n + 2i + 1 + h=0 m2h+1 + h=1 mh , . . . , n + 2i + mi + h=0 m2h+1 + Pi−1 h=1 mh }, dan untuk i = 1, 2, 3, . . . , n − 1, Bi = f (ui ) + f (ui+1 ) = n + m1 + 2i + 1 +

Pα

h=0

m2h+1 +

Tampak bahwa untuk i = 1, 2, 3, . . . , n, Bi = maks(Ai ) + 1

39

Pi

h=2

mh .

dan untuk i = 1, 2, 3, . . . , n − 1, min(Ai+1 ) = Bi + 1. Berdasarkan hal ini dan karena Ai , i = 1, 2, 3, . . . , n, himpunan bilangan yang berurutan, maka S = {f (x) + f (y)|xy ∈ E(F C(m1 , m2 , . . . , mn ))} adalah himpunan P bilangan bulat berurutan dengan maks(S) = p + n + αh=0 m2h+1 . Jadi f dapat diperluas menjadi suatu pelabelan ajaib super pada F C(m1 , m2 , . . . , mn ) dengan P konstanta ajaib 2p + n + 1 + αh=0 m2h+1 . 2

Pelabelan titik dari graf kembang api F C(1, 3, 4, 6, 7, 8, 9) ditunjukkan pada Gambar III.9

Gambar III.9. Pelabelan titik dari graf kembang api

Berdasarkan Teorema III.9 dan Lemma III.7, didapatkan akibat berikut. Akibat III.7  Jika m1 ≤ m2 ≤ m3 ≤ . . . ≤ mn , maka F C(m1 , m2 , . . . , mn ) P merupakan graf ajaib super dengan konstanta ajaib 3p − n + 1 − αh=0 m2h+1 . Berdasarkan sifat dualitas (Lemma III.1), F C(m1 , m2 , . . . , mn ) juga mempunyai suatu pelabelan ajaib seperti dinyatakan pada akaibat berikut. Akibat III.8  Jika m1 ≤ m2 ≤ m3 ≤ . . . ≤ mn , maka F C(m1 , m2 , . . . , mn ) P mempunyai pelabelan ajaib dengan konstanta ajaib 4p − n − 1 − αh=0 m2h+1 atau P 3p + n − 1 + αh=0 m2h+1 . Teorema III.9 memperumum hasil yang didapatkan oleh Swaminathan dan Jeyanthi (2006), tetapi hasil tersebut belum meliputi seluruh graf kembang api yang ada. Oleh karena itu, kami kemukakan masalah terbuka berikut.

40

Masalah Terbuka III.3 Carilah suatu pelabelan ajaib super untuk setiap graf kembang api. Selanjutnya, kami mengkaji graf lobster H yang mempunyai struktur seperti pada Gambar III.10. Graf tersebut dinotasikan dengan L(l1m1 ,m2 , l2m2 ,m3 , . . . , lnmn ,mn+1 ).

Gambar III.10. Graf lobster dengan struktur tertentu m ,m m ,m m ,m Himpunan titik dan himpunan sisi dari H ∼ = L(l1 1 2 , l2 2 3 , . . . , l1 n n+1 ) didefini-

sikan berikut. k |1 ≤ i ≤ n, 1 ≤ k ≤ mi } V (H) = {ui |1 ≤ i ≤ n} ∪ {vi,j |1 ≤ i ≤ n, j = 1, 2} ∪ {vi,1 k ∪ {vi,2 |1 ≤ i ≤ n, 1 ≤ k ≤ mi+1 } ∪ {wi,h |1 ≤ i ≤ n, 1 ≤ h ≤ li },

dan E(H) = {ui ui+1 |1 ≤ i ≤ n − 1} ∪ {ui vi,j |1 ≤ i ≤ n, j = 1, 2} k k ∪{vi,1 vi,1 |1 ≤ i ≤ n, 1 ≤ k ≤ mi } ∪ {vi,2 vi,2 |1 ≤ i ≤ n, 1 ≤ k ≤ mi+1 }

∪{ui wi,h |1 ≤ i ≤ n, 1 ≤ h ≤ li }. Teorema III.10  Untuk setiap li ≥ 0, 1 ≤ i ≤ n, dan setiap mi ≥ 1, 1 ≤ i ≤ m ,m m ,m m ,m n + 1, H ∼ = L(l1 1 2 , l2 2 3 , . . . , l1 n n+1 ) merupakan graf ajaib super.

Bukti: Misalkan λ dan µ adalah dua konstanta yang didefinisikan seperti di bawah ini. µ

bnc

2 X X 3n λ=b c+ mt + l2t , 2 t=1 t=1

dengan   n + 1, jika n ganjil, µ=  n, jika n genap.

41

Selanjutnya perhatikan pelabelan titik f : V (H) → {1, 2, 3, . . . , p}, p = 3n + Pn Pn Pn+1 i=1 li + i=1 mi + i=2 mi , yang didefinisikan sebagai berikut.  i−1  1 (3i − 1) + Pi m + P 2 l , jika i ganjil, t t=1 2t t=1 2 f (ui ) = i−2  λ + 3i + Pi m + P 2 l jika i genap. 2t+1 , t t=0 t=2 2  i−3  λ + 1 (3i − 1) + Pi m + P 2 l t 2t+1 , jika i ganjil, t=0 t=2 2 f (vi,1 ) = i−2 P P  1 (3i − 2) + i m + 2 jika i genap. t t=1 l2t , t=1 2 f (vi,2 ) = f (vi,1 ) + li + 1, untuk semua i. Semua titik pendan diberi label seperti dinyatakan formula berikut.

 i−1  3 (i − 1) + k + Pi−1 m + P 2 l , jika i ganjil, 1 ≤ k ≤ mi , t t=1 2t t=1 2 k f (vi,1 )= i−2 P P  λ + 1 (3i − 2) + k + i−1 m + 2 t t=0 l2t+1 , jika i genap, 1 ≤ k ≤ mi . t=2 2

 i−1  1 (3i − 1) + k + Pi m + P 2 l , jika i ganjil, 1 ≤ k ≤ m , t i+1 t=1 2t t=1 2 k f (vi,2 )= i−2 P P  λ + 3i + k + i m + 2 jika i genap, 1 ≤ k ≤ mi+1 . t t=0 l2t+1 , t=2 2

f (wi,h ) = f (vi,1 ) + h, untuk semua 1 ≤ i ≤ n, dan 1 ≤ h ≤ li . Terhadap pelabelan f jumlah dua label titik yang bertetangga dapat dinyatakan sebagai berikut. k f (v1,1 ) + f (v1,1 ) = λ + k + 1, 1 ≤ k ≤ m1 , k f (vi,1 ) + f (vi,1 )

= λ + k + m1 − 2 + 3i + mi + 2

Pi−1

Pi−1

2 ≤ i ≤ n dan 1 ≤ k ≤ mi , Pi−1 f (ui ) + f (vi,1 ) = λ + m1 + 3i − 1 + 2 t=2 mt + t=1 lt , 1 ≤ i ≤ n, P Pi−1 f (ui )+f (wi,h ) = λ+m1 +h−1+3i+2 it=2 mt + t=1 lt , 1 ≤ i ≤ n, dan 1 ≤ h ≤ li , Pi Pi−1 f (ui ) + f (vi,2 ) = λ + m1 + 3i + li + 2 t=2 mt + t=1 lt , 1 ≤ i ≤ n, t=2

mt + Pi

t=1 lt ,

k f (vi,2 ) + f (vi,2 )

= λ + k − m1 + 3i + li + 2

Pi

Pi−1

≤ i ≤ n, dan 1 ≤ k ≤ mi+1 , dan Pi P f (ui ) + f (ui+1 ) = λ − m1 + 1 + 3i + mi+1 + 2 t=1 mt + it=1 lt , 1 ≤ i ≤ n − 1. t=2

mt +

t=1 lt , 1

42

Untuk i = 1, 2, 3, . . . , n, misalkan

k Ai = f (vi,1 ) + f (vi,1 ), 1 ≤ k ≤ mi ,

Bi = f (ui ) + f (vi,1 ),

Ci = f (ui ) + f (wi,h ), 1 ≤ h ≤ li , Di = f (ui ) + f (vi,2 ),

k ), 1 ≤ k ≤ mi+1 , Ei = f (vi,2 ) + f (vi,2

dan untuk i = 1, 2, 3, . . . , n − 1, Fi = f (ui ) + f (ui+1 ). Maka, min(A1 ) = λ + 2, dan maks(A1 ) = λ + m1 + 1, untuk i = 2, 3, . . . , n,

min(Ai ) = λ + m1 − 1 + 3i + mi + 2

i−1 X

i−1 X

mt +

t=1

t=2

maks(Ai ) = λ + m1 − 2 + 3i + 2mi + 2

lt ,

i−1 X

mt +

t=2

i−1 X

lt ,

t=1

dan untuk i = 1, 2, 3, . . . , n,

min(Ci ) = λ + m1 + 3i + 2

i X

mt +

i−1 X

t=2

t=1

maks(Ci ) = λ + m1 − 1 + 3i + li + 2

min(Ei ) = λ − m1 + 1 + 3i + li + 2

lt ,

i X

i−1 X

mt +

t=2

t=1

i X

i−1 X

mt +

t=1

maks(Ei ) = λ − m1 + 3i + li + mi+1 + 2

i X

lt ,

lt ,

t=1

mt +

t=1

i−1 X

lt .

t=1

Tampak bahwa untuk i = 1, 2, 3, . . . , n berlaku Bi = maks(Ai ) + 1, min(Ci ) = Bi + 1, Di = maks(Ci ) + 1, min(Ei ) = Di + 1, Fi = maks(Ei ) + 1, 43

dan untuk i = 1, 2, 3, . . . , n − 1 min(Ai+1 ) = Fi . Karena hal ini dan karena Ai , Ci , dan Ei adalah himpunan bilangan berurutan, maka S = {f (x) + f (y)|xy ∈ E(G2 )} adalah himpunan bilangan bulat berurutan dengan maks(S) = p + λ. Berdasarkan Lemma III.4, f dapat diperluas menjadi suatu pelabelan ajaib super pada H dengan konstanta ajaib 2p + 1 + λ.

2

Pelabelan titik dari L(33,1 , 21,2 , 42,1 , 21,3 , 33,4 ) ditunjukkan pada Gambar III.11.

Gambar III.11. Pelabelan titik dari graf lobster yang mempunyai struktur seperti graf lobster pada Gambar III.10.

Berdasarkan sifat pelabelan dual super (Lemma III.7) didapat akibat berikut. Akibat III.9  Untuk setiap li ≥ 0, 1 ≤ i ≤ n, dan setiap mi ≥ 1, 1 ≤ i ≤ m ,m m ,m m ,m n + 1, H ∼ = L(l1 1 2 , l2 2 3 , . . . , l1 n n+1 ) mempunyai pelabelan ajaib super dengan

konstanta ajaib 3p + 1 − λ. Berdasarkan fakta tersebut dan Lemma III.1 didapat akibat berikut. Akibat III.10  Untuk setiap li ≥ 0, 1 ≤ i ≤ n, dan setiap mi ≥ 1, 1 ≤ i ≤ n + 1, m ,m m ,m m ,m H ∼ = L(l1 1 2 , l2 2 3 , . . . , l1 n n+1 ) mempunyai pelabelan ajaib dengan konstanta

ajaib 4p − 1 − λ atau 3p − 1 + λ.

III.4.4

Pelabelan ajaib pada graf rantai

Block-cut-vertex graph dari suatu graf G adalah graf H yang titik-titiknya adalah blok dan titik potong dari G dimana dua titik bertetangga di H jika dan hanya jika satu titik berupa titik potong (di G) dan titik yang lain adalah blok (di G) yang memuat titik potong tersebut. Graf rantai didefinisikan sebagai graf yang terdiri dari B1 , B2 , B3 , . . . , Bk blok, k ≥ 2, sehingga untuk setiap i, 1 ≤ i ≤ k − 1, Bi 44

dan Bi+1 beririsan pada tepat satu titik sehingga block cut-vertex graph-nya adalah graf lintasan. Graf rantai pertama kali diperkenalkan oleh Barrientos (2002). Graf rantai yang setiap bloknya adalah graf F dinotasikan dengan kF -lintasan.

Pelabelan ajaib dari graf rantai sudah dikaji oleh beberapa peneliti. Misalnya, Lee dan Wang (2003) mengkaji pelabelan ajaib super pada graf rantai dimana setiap bloknya berupa graf lengkap Kn untuk suatu n. Pada subbab ini, kami mengkaji pelabelan ajaib dari graf rantai dimana setiap bloknya merupakan graf siklus C4 .

Misalkan G adalah kCn -lintasan dengan k ≥ 2. Misalkan u1 , u2 , . . . , uk−1 adalah titik potong dari G. Misalkan di menyatakan jarak antara ui dan ui+1 di G, 1 ≤ i ≤ k −2. (k − 2)-tuple (d1 , d2 , . . . , dk−2 ) disebut string dari G. String ini menentukan struktur dari G. Graf kCn -lintasan terdiri dari nk sisi dan (n − 1)k + 1 titik. Dari (n − 1)k + 1 titik tersebut, k − 1 titik berderajat 4 dan titik yang lain berderajat 2.

Selanjutnya, kami hanya memperhatikan kC4 -lintasan saja. Suatu kC4 -lintasan dapat dibentuk dari (k − 1)C4 -lintasan. Terdapat 2 buah kC4 -lintasan yang berbeda yang dapat dibentuk dari (k − 1)C4 -lintasan. Sebagai contoh dua buah 3C4 -lintasan yang berbeda (Gambar III.12 (a) dan (b)) yang dibentuk dari 2C4 -lintasan (Gambar III.12 (c)) ditunjukkan pada Gambar III.12.

Gambar III.12. Pembentukkan 3C4 -lintasan dari 2C4 -lintasan

Berbagai pelabelan graf telah dikaji untuk kC4 -lintasan, misalnya pelabelan graceful dan pelabelan-α (Barientos, 2004). Pada subbab ini akan dikaji pelabelan ajaib pada kC4 -lintasan. Misalkan kC4 -lintasan mempunyai suatu pelabelan ajaib dengan konstanta ajaib c, maka dengan argumen yang sama seperti pada Lemma III.8 kita mempunyai 4kc ≥

7k+1 X

i+3

i=1

k−1 X i=1

45

i+

3k+1 X i=k

i,

dan 4kc ≤

7k+1 X i=1

i+

6k+2 X

i+3

i=4k+1

7k+1 X

i.

i=6k+3

Jadi lemma berikut benar. Lemma III.10  Jika kC4 -lintasan merupakan graf ajaib, maka konstanta ajaib c terletak pada interval berikut: 1 (15k 2 2k

+ 7k + 1) ≤ c ≤

1 (27k 2 2k

+ 5k − 1).

2

Pada tiga teorema berikut akan ditunjukkan bahwa H ∼ = kC4 -lintasan dengan string (2, 2, 2, . . . , 2) mempunyai suatu pelabelan ajaib. Sebelumnya, misalkan himpunan titik dan himpunan sisi dari H didefinisikan sebagai berikut. V (H) = {ui |1 ≤ i ≤ k + 1} ∪ {vi |1 ≤ i ≤ 2k} dan E(H) = {ui vi |1 ≤ i ≤ k} ∪ {vi ui+1 |1 ≤ i ≤ k} ∪ {ui vi+k |1 ≤ i ≤ k} ∪ {vk+i ui+1 |1 ≤ i ≤ k}. Berdasarkan pendefinisian ini, u2 , u3 , . . . , uk adalah titik potong dari H. Teorema III.11  Untuk setiap k ≥ 2, H ∼ = kC4 -lintasan dengan string (2, 2, 2, . . . , 2) merupakan graf ajaib dengan konstanta ajaib 8k + 4. Bukti: Perhatikan pelabelan f1 : V (H) ∪ E(H) → {1, 2, 3, . . . , 7k + 1} yang didefinisikan sebagai berikut.    i,       4k + 1 + i,       1 + i,   f1 (x) = 4k + 3 − 2i,      4k + 2 − 2i,       7k + 3 − 2i,      7k + 2 − 2i,

jika x = ui untuk 1 ≤ i ≤ k + 1, jika x = vi untuk 1 ≤ i ≤ k, jika x = vi untuk k + 1 ≤ i ≤ 2k, jika x = ui vi untuk 1 ≤ i ≤ k, jika x = vi ui+1 untuk 1 ≤ i ≤ k, jika x = ui vk+i untuk 1 ≤ i ≤ k, jika x = vk+i ui+1 untuk 1 ≤ i ≤ k.

Kemudian perhatikan bahwa f1 (ui ) + f1 (ui vi ) + f1 (vi ) = i + (4k + 3 − 2i) + (4k + 1 + i) = 8k + 4, 46

f1 (vi ) + f1 (vi ui+1 ) + f1 (ui+1 ) = (4k + 1 + i) + (4k + 2 − 2i) + (i + 1) = 8k + 4, f1 (ui ) + f1 (ui vk+i ) + f1 (vk+i ) = i + (7k + 3 − 2i) + (i + k + 1) = 8k + 4, f1 (vk+i ) + f1 (vk+i ui+1 ) + f1 (ui+1 ) = (i + k + 1) + (7k + 2 − 2i) + (i + 1) = 8k + 4. Jadi f1 adalah suatu pelabelan ajaib pada H dengan konstanta ajaib 8k + 4.

2

Teorema III.12  Untuk semua k ≥ 2, H ∼ = kC4 -lintasan dengan string (2, 2, 2, . . . , 2) merupakan graf ajaib dengan konstanta ajaib 9k + 4. Bukti: Definisikan pelabelan f2 sebagai berikut.

f2 (x) =

   i,       6k + 1 + i,       2k + 1 + i,  

3k + 3 − 2i,      3k + 2 − 2i,       6k + 3 − 2i,      6k + 2 − 2i,

jika x = ui untuk 1 ≤ i ≤ k + 1, jika x = vi untuk 1 ≤ i ≤ k, jika x = vi untuk k + 1 ≤ i ≤ 2k, jika x = ui vi untuk 1 ≤ i ≤ k, jika x = vi ui+1 untuk 1 ≤ i ≤ k, jika x = ui vk+i untuk 1 ≤ i ≤ k, jika x = vk+i ui+1 untuk 1 ≤ i ≤ k.

Dengan argumen yang sama seperti pada Teorema III.11 dapat diperiksa bahwa f2 adalah suatu pelabelan ajaib dari V (H) ∪ E(H) ke {1, 2, 3, . . . , 7k + 1} dengan konstanta ajaib 9k + 4.

2

Selanjutnya perhatikan pelabelan f3 yang didefinisikan sebagai berikut.    3k + i,       i,       3k + 1 + i,   f3 (x) = 7k + 3 − 2i,      7k + 2 − 2i,       3k + 2 − 2i,      3k + 1 − 2i,

jika x = ui untuk 1 ≤ i ≤ k + 1, jika x = vi untuk 1 ≤ i ≤ k, jika x = vi untuk k + 1 ≤ i ≤ 2k, jika x = ui vi untuk 1 ≤ i ≤ k, jika x = vi ui+1 untuk 1 ≤ i ≤ k, jika x = ui vk+i untuk 1 ≤ i ≤ k, jika x = vk+i ui+1 untuk 1 ≤ i ≤ k.

Sekali lagi, dengan argumen yang sama seperti pada Teorema III.11 dapat diperiksa bahwa f3 merupakan suatu pelabelan ajaib pada H dengan konstanta ajaib 10k + 3. Jadi teorema berikut benar. 47

Teorema III.13  Untuk semua k ≥ 2, H adalah graf ajaib dengan konstanta 2

ajaib 10k + 3.

Berdasarkan Teorema III.11, III.12, dan III.13 dan Lemma III.1, didapat akibat berikut. Akibat III.11  Untuk semua k ≥ 2, H adalah graf ajaib dengan konstanta ajaib 13k + 2, 12k + 2, atau 11k + 3.

2

Hasil-hasil di atas menunjukkan bahwa untuk 6 konstanta yang berbeda (termasuk dualnya), kC4 -lintasan dengan string (2, 2, 2, . . . , 2) merupakan graf ajaib. Masalah Terbuka III.4 Carilah pelabelan ajaib pada kC4 -lintasan dengan string (2, 2, 2, . . . , 2) untuk konstanta ajaib yang lain. Selanjutnya akan ditunjukkan bahwa untuk k genap F ∼ = kC4 -lintasan dengan string (1, 1, 1, . . . , 1) merupakan graf ajaib. Untuk itu, definisikan F ∼ = kC4 -lintasan dengan string (1, 1, 1, . . . , 1) sebagai graf dengan himpunan titik dan himpunan sisi sebagai berikut. V (F ) = {ui |1 ≤ i ≤ k + 1} ∪ {vi |1 ≤ i ≤ k} ∪ {wi |1 ≤ i ≤ k} dan E(F ) = {ui ui+1 |1 ≤ i ≤ k} ∪ {ui vi |1 ≤ i ≤ k} ∪ {vi vi+1 |i = 1, 3, 5, . . . , k − 1} ∪ {wi wi+1 |i = 1, 3, 5, . . . , k − 1} ∪ {ui+1 wi |1 ≤ i ≤ k}. Terhadap pendefinisian ini, u2 , u3 , . . . , uk merupakan titik potong dari F . Teorema III.14  Jika k genap, k ≥ 2, maka F ∼ = kC4 -lintasan dengan string (1, 1, 1, . . . , 1) mempunyai pelabelan ajaib dengan konstanta ajaib 12 (17k + 10). Bukti: Labelkan titik dan sisi di F dengan cara sebagai berikut.    7k + 1, jika i = 1,   1 g1 (ui ) = (3k + 4i − 2), jika i = 3, 5, . . . , k + 1, 2     1 (3i − 2), jika i = 2, 4, 6, . . . , k. 2

48

  3 (i + 1), jika i = 1, 3, 5, . . . , k − 1, 2 g1 (vi ) =  1 (3k + 4i + 4), jika i = 2, 4, 6, . . . , k. 2   1 (14k − 7i + 7), jika i = 1, 3, 5, . . . , k − 1, 2 g1 (wi ) =  1 (3i − 4), jika i = 2, 4, 6, . . . , k. 2  1   (3k + 2), jika i = 1,   2 1 g1 (ui vi ) = (14k − 7i + 9), jika i = 3, 5, . . . , k − 1, 2     1 (14k − 7i + 8), jika i = 2, 4, 6, . . . , k. 2  1   (3k + 4), jika i = 1,   2 1 g1 (ui ui+1 ) = (14k − 7i + 11), jika i = 3, 5, . . . , k − 1, 2     1 (14k − 7i + 10), jika i = 2, 4, 6, . . . , k. 2   1 (3k + 4i + 2), jika i = 1, 3, 5, . . . , k − 1, 2 g1 (ui+1 wi ) =  1 (14k − 7i + 12), jika i = 2, 4, 6, . . . , k. 2 1 g1 (vi vi+1 ) = (14k − 7i − 1), jika i = 1, 3, 5, . . . , k − 1. 2 1 g1 (wi wi+1 ) = (3k + 4i + 4), jika i = 1, 3, 5, . . . , k − 1. 2 Perhatikan bahwa g1 (u1 ) + g1 (u1 u2 ) + g1 (u2 ) = (7k + 1) + 12 (3k + 4) + 2 = 12 (17k + 10), untuk i = 3, 5, 7, . . . , k − 1 g1 (ui )+g1 (ui ui+1 )+g1 (ui+1 ) = 12 (3k+4i−2)+ 12 (14k−7i+11)+ 12 (3i+1) = 12 (17k+10), untuk i = 2, 4, 6, . . . , k g1 (ui )+g1 (ui ui+1 )+g1 (ui+1 ) = 21 (3i−2)+ 12 (14k−7i+10)+ 21 (3k+4i+2) = 12 (17k+10).

g1 (u1 ) + g1 (u1 v1 ) + g1 (v1 ) = (7k + 1) + 12 (3k + 2) + 3 = 12 (17k + 10), untuk i = 3, 5, 7, . . . , k − 1 g1 (ui ) + g1 (ui vi ) + g1 (vi ) = 12 (3k + 4i − 2) + 12 (14k − 7i + 9) + 12 (3i + 3) = 12 (17k + 10), untuk i = 2, 4, 6, . . . , k g1 (ui ) + g1 (ui vi ) + g1 (vi ) = 21 (3i − 2) + 12 (14k − 7i + 8) + 12 (3k + 4i + 4) = 12 (17k + 10).

49

g1 (u2 ) + g1 (u2 w1 ) + g1 (w1 ) = 2 + 12 (3k + 6) + 7k = 21 (17k + 10), untuk i = 3, 5, 7, . . . , k − 1 g1 (ui+1 )+g1 (ui+1 wi )+g1 (wi ) = 12 (3i+1)+ 12 (3k+4i+2)+ 21 (14k−7i+7) = 12 (17k+10), untuk i = 2, 4, 6, . . . , k g1 (ui+1 ) + g1 (ui+1 wi ) + g1 (wi ) = 12 (3k + 4i + 2) + 12 (14k − 7i + 12) + 21 (3i − 4) = 1 (17k 2

+ 10).

Untuk i = 1, 3, 5, . . . , k − 1 g1 (vi )+g1 (vi vi+1 )+g1 (vi+1 ) = 21 (3i+3)+ 12 (14k−7i−1)+ 12 (3k+4i+8) = 12 (17k+10), g1 (wi )+g1 (wi wi+1 )+g1 (wi+1 ) = 21 (14k−7i+7)+ 12 (3k+4i+4)+ 12 (3i−1) = 12 (17k+10). Tampak bahwa g1 (x)+g1 (xy)+g1 (y) = 21 (17k+10) untuk setiap sisi xy di F . Jadi g1 merupakan suatu pelabelan ajaib pada F dengan konstanta ajaib 21 (17k +10).

2

Terdapat cara yang lain untuk melabeli F ∼ = kC4 -lintasan dengan string (1, 1, 1, . . . , 1) untuk k genap, seperti dinyatakan pada dua teorema berikut. Teorema III.15  Jika k genap, k ≥ 2, maka F ∼ = kC4 -lintasan dengan string (1, 1, 1, . . . , 1) mempunyai pelabelan ajaib dengan konstanta ajaib 9k + 7. Bukti: Definisikan pelabelan g2 : V (F ) ∪ E(F ) → {1, 2, 3, . . . , 7k + 1} sedemikian hingga    7k + 1, jika i = 1,   g2 (ui ) = 2i − 1, jika i = 3, 5, . . . , k + 1,     1 (4k + 3i + 2), jika i = 2, 4, 6, . . . , k. 2   1 (4k + 3i + 7), jika i = 1, 3, 5, . . . , k − 1, 2 g2 (vi ) =  2i + 2, jika i = 2, 4, 6, . . . , k.   g (w ), jika i = 1, 3, 5, . . . , k − 1, 1 i g2 (wi ) =  1 (4k + 3i), jika i = 2, 4, 6, . . . , k. 2   1, jika i = 1, g2 (ui vi ) =  g (u v ), jika i 6= 1. 1 i i

50

  2, g2 (ui ui+1 ) =  g (u u 1

i i+1 ),

jika i = 1, jika i 6= 1.

  2i + 1, jika i = 1, 3, 5, . . . , k − 1, g2 (ui+1 wi ) =  g (u w ), jika i = 2, 4, 6, . . . , k. 1 i+1 i g2 (vi vi+1 ) = g1 (vi vi+1 )

g2 (wi wi+1 ) = 2i + 2, jika i = 1, 3, 5, . . . , k − 1. Dengan cara yang sama seperti pada Teorema III.14, dapat diperiksa bahwa g2 adalah suatu pelabelan ajaib pada F dengan konstanta ajaib 9k + 7.

2

Teorema III.16  Jika k genap, k ≥ 2, maka F ∼ = kC4 -lintasan dengan string (1, 1, 1, . . . , 1) mempunyai pelabelan ajaib dengan konstanta ajaib 12k + 1. Bukti: Definisikan pelabelan g3 : V (F ) ∪ E(F ) → {1, 2, 3, . . . , 7k + 1} sedemikian hingga  1   (7k − 2), jika i = 1,   2 g3 (ui ) = 5k + 2i − 2, jika i = 3, 5, . . . , k + 1,     1 (7k + 3i − 4), jika i = 2, 4, 6, . . . , k. 2   1 (7k + 3i + 1), jika i = 1, 3, 5, . . . , k − 1, 2 g3 (vi ) =  5k + 2i + 1, jika i = 2, 4, 6, . . . , k.   1 (7k − 7i + 3), jika i = 1, 3, 5, . . . , k − 1, 2 g3 (wi ) =  1 (7k + 3i − 6), jika i = 2, 4, 6, . . . , k. 2    5k, jika i = 1,   1 g3 (ui vi ) = (7k − 7i + 5), jika i = 3, 5, . . . , k − 1, 2     1 (7k − 7i + 4), jika i = 2, 4, 6, . . . , k. 2    5k + 1, jika i = 1,   1 g3 (ui ui+1 ) = (7k − 7i + 7), jika i = 3, 5, . . . , k − 1, 2     1 (7k − 7i + 6), jika i = 2, 4, 6, . . . , k. 2

51

  5k + 2i, jika i = 1, 3, 5, . . . , k − 1, g3 (ui+1 wi ) =  1 (7k − 7i + 8), jika i = 2, 4, 6, . . . , k. 2 1 g3 (vi vi+1 ) = (7k − 7i − 5), jika i = 1, 3, 5, . . . , k − 1. 2

g3 (wi wi+1 ) = 5k + 2i + 1, jika i = 1, 3, 5, . . . , k − 1. Dengan cara yang sama seperti pada Teorema III.14, dapat ditunjukkan bahwa g3 adalah suatu pelabelan ajaib pada F dengan konstanta ajaib 12k + 1.

2

Berdasarkan tiga teorema tersebut dan Lemma III.1 didapat akibat berikut. Akibat III.12  Jika k genap, k ≥ 2, maka F ∼ = kC4 -lintasan dengan string (1, 1, 1, . . . , 1) mempunyai pelabelan ajaib dengan konstanta ajaib 21 (25k +2), 12k −1 atau 9k + 5. Pelabelan ajaib dari 4C4 -lintasan dengan string (2, 2, 2, . . . , 2) dengan konstanta ajaib 40 dan 6C4 -lintasan dengan string (1, 1, 1, . . . , 1) dengan konstanta ajaib 56 berturut-turut ditunjukkan pada Gambar III.13(a) dan (b).

Gambar III.13. Pelabelan ajaib pada kC4 -lintasan

Kami belum dapat menemukan suatu pelabelan ajaib bagi kC4 -lintasan dengan string (1, 1, 1, . . . , 1) untuk k ganjil, k ≥ 3. Oleh karena itu, kami mempunyai masalah terbuka berikut. Masalah Terbuka III.5 Periksa apakah ada pelabelan ajaib pada kC4 -lintasan dengan string (1, 1, 1, . . . , 1) untuk k ganjil, k ≥ 3. 52

Secara umum, kami mempunyai masalah terbuka berikut. Masalah Terbuka III.6 Periksa apakah ada pelabelan ajaib pada kC4 -lintasan dengan string (d1 , d2 , d3 , . . . , dk−2 ) dengan di ∈ {1, 2}, 1 ≤ i ≤ k − 2. Semua pelabelan yang telah ditunjukkan merupakan pelabelan ajaib, tetapi bukan pelabelan ajaib super. Kami hanya mendapatkan pelabelan ajaib super untuk kC4 -lintasan hanya untuk kC4 -lintasan dengan string (2, 2, 2, . . . , 2) dimana 2 ≤ k ≤ 5. Untuk k = 5, jika titik (u1 , u2 , u3 , u4 , u5 , u6 ) diberi label (1, 2, 6, 9, 12, 11) dan titik (v1 , v2 , v3 , v4 , v5 , v6 , v7 , v8 , v9 , v10 ) diberi label (7, 5, 4, 13, 8, 16, 10, 15, 14, 3), maka berdasarkan Lemma III.4, pelabelan tersebut merupakan pelabelan ajaib super dari 5C4 -lintasan dengan string (2, 2, 2, . . . , 2) dengan konstanta ajaib 43. Kami menduga bahwa untuk k ≥ 6, kC4 -lintasan dengan string (2, 2, 2, . . . , 2) mempunyai suatu pelabelan ajaib super. Konjektur III.3 Untuk setiap k ≥ 2, kC4 -lintasan dengan string (2, 2, 2, . . . , 2) merupakan graf ajaib super. Masalah Terbuka III.7 Periksa apakah untuk setiap k ≥ 2, kC4 -lintasan dengan string (d1 , d2 , d3 , . . . , dk−2 ) dengan di ∈ {1, 2}, 1 ≤ i ≤ k − 2, merupakan graf ajaib super. Masalah Terbuka III.8 Periksa apakah untuk setiap k ≥ 2, kCn -lintasan dengan string (d1 , d2 , d3 , . . . , dk−2 ) dengan di ∈ {1, 2, . . . , b n2 c}, 1 ≤ i ≤ k − 2, merupakan graf ajaib (super).

53