PELABELAN πΈ π π· π β SUPER GRACEFUL β SISI PADA GRAF KUBUS HIPER πΈπ UNTUK π β€ π Destian Dwi Asyani1, Bayu Surarso2, Robertus Heri Soelistyo Utomo3 1,2,3 Jurusan Matematika Fakultas Sains dan Matematika, Universitas Diponegoro Jl. Prof. H. Soedarto,SH. Tembalang Semarang 50275, Indonesia
[email protected] ABSTRAK Misalkan πΊ = (π(πΊ), πΈ(πΊ)) merupakan suatu graf sederhana, berhingga dan tak berarah dengan π = π(πΊ) dan = πΈ(πΊ) . Jika π dan π bilangan asli maka π(π) dan πβ2 π(π) didefinisikan untuk π genap maka π π = Β±π, β¦ , Β± π + 2 , untuk π ganjil maka π π = 0, Β±π, Β± π + 1 , β¦ , Β± π + π π = Β±π, Β± π + 1 , β¦ , Β± π + πβ3
πβ2 2
dan
πβ3 2
untuk π
, untuk π genap maka ganjil
maka π π =
0, Β±π, Β± π + 1 , β¦ , Β± π + 2 . Sebuah graf πΊ adalah graf π π π(π) β ππΊπ jika terdapat pemetaan injektif π: πΈ πΊ β π(π) sedemikian sehingga π β : π πΊ β π(π) yang didefinisikan oleh π β π£ = π’π£ππΈ πΊ π π’π£ adalah pemetaan surjektif. Graf kubus hiper π1 dan graf kubus hiper π2 adalah bukan graf π π π(π) β ππΊπ . Hubungan nilai π dan π sehingga graf kubus hiper π3 merupakan graf π π π(π) β ππΊπ adalah jika π = 1 maka 1 β€ π β€ 7, jika π = 2 maka 1 β€ π β€ 7 dan jika π β₯ 3 maka π = 9 and π β 2 β€ π β€ π + 4 . Kata Kunci : pelabelan π π π(π) β ππΊπ, graf kubus hiper. 1. PENDAHULUAN Terdapat banyak pokok bahasan dalam teori graf, salah satunya adalah pelabelan graf. Pelabelan graf sudah banyak dikaji sejak pertengahan tahun 1960-an dan pertama kali diperkenalkan oleh SadlΓ Δk (1964), lalu Stewart (1966), Kotzig dan Rosa (1967). Pelabelan dari graf merupakan pemetaan yang memetakan unsur β unsur graf (titik atau sisi) ke bilangan (umumnya bilangan bulat positif) yang disebut label. Pada umumnya domain dari pemetaan ini adalah himpunan titik saja (pelabelan titik), himpunan sisi saja (pelabelan sisi), atau keduanya (pelabelan total). Pelabelan graceful merupakan salah satu jenis pelabelan graf yang telah dikembangkan. Dalam pengembangannya, dikenal pula Pelabelan Ξ± (Balanced Labeling), Pelabelan k-graceful, Pelabelan Skolem-Graceful, Pelabelan Graceful Ganjil dan Pelabelan Cordial. Pelabelan graceful adalah salah satu yang luas penggunaannya, terutama diaplikasikan dalam radar, jaringan komunikasi, desain sirkuit, teori koding, astronomi dan kristalografi. Studi tentang graf graceful dan
29
metode pelabelan graceful diperkenalkan oleh Rosa pada tahun 1967. Sebuah graf πΊ dengan π titik dan π sisi dikatakan graceful jika terdapat sebuah pemetaan injektif π: π(πΊ) β {0,1,2, β¦ , π} sehingga diperoleh π β : πΈ(πΊ) β {0,1,2, β¦ , π} dimana π β (π’π£) = π(π’) β π(π£) adalah pemetaan surjektif. Sebuah graf yang berlaku pelabelan graceful disebut graf graceful. Graf Kubus hiper ( kubus βπ ) dapat direpresentasikan sebagai graf tak berarah ππ = (π, πΈ) dimana π adalah himpunan titik yang memuat 2π titik yang diberi label sebagai bilangan biner dengan banyaknya titik π dari 00 β¦ 0 ke 11 β¦ 1 π
π
dan πΈ adalah himpunan sisi yang menghubungkan dua titik jika hanya jika titik β titik tersebut berbeda tepat satu bit dari labelnya. Dengan demikian, masing β masing titik memiliki hubungan langsung dengan π titik lainnya dan dengan mudah ditunjukkan bahwa πΈ = π2πβ1 . Beberapa kajian terdahulu tentang pelabelan graceful telah dilakukan oleh Triyas Lestari [1] dalam tugas akhirnya yang berjudul βPelabelan Graceful dan Graceful Ganjil pada Graf Path, Graf Sikel, Gabungan Graf Sikel dan Graf Pathβ. Tulisan ini melanjutkan kajian tentang pelabelan graceful yaitu pelabelan π(π) π(π) β super graceful β sisi pada graf kubus hiper ππ untuk π β€ 3. 2. PELABELAN πΈ(π) π·(π) β SUPER GRACEFUL-SISI Definisi 2.1 [2] Untuk suatu graf πΊ dengan himpunan titik π(πΊ) dan himpunan sisi πΈ(πΊ), dengan π = π(πΊ) dan π = πΈ(πΊ) . Jika π dan π bilangan asli maka π(π) dan π(π) didefinisikan πβ2 Β±π, Β± π + 1 , β¦ , Β± π + 2 , jika π genap π π =
... (3.3) 0, Β±π, Β± π + 1 , β¦ , Β± π + Β±π, Β± π + 1 , β¦ , Β± π +
πβ3 2
πβ2
, jika π ganjil , jika π genap
2
π π =
... (3.4) 0, Β±π, Β± π + 1 , β¦ , Β± π +
πβ3 2
, jika π ganjil
Sebuah graf πΊ adalah graf π(π) π(π) β super graceful-sisi jika terdapat pemetaan injektif π: πΈ πΊ β π(π) sedemikian sehingga π β : π πΊ β π(π) didefinisikan oleh πβ π£ =
π’π£ππΈ πΊ
Contoh 2.1
30
π π’π£ adalah pemetaan surjektif.
Sebagai contoh diberikan graf πΆ5 dengan π(πΊ) = {π£1 , π£2 , π£3 , π£4 , π£5 , π£6 } dan πΈ(πΊ) = π£1 π£2 , π£2 π£3 , π£3 π£4 , π£4 π£5 , π£5 π£1 , maka π = 5 dan π = 5. Akan dibuktikan bahwa graf tersebut adalah graf π(π) π(π) β super graceful-sisi dengan mengambil kasus π = 2 dan π = 1, sehingga dari (3.3) dan (3.4) diperoleh π(2) = {0 , Β±2, Β±3} dan π 1 = {0, Β±1, Β±2} . Misalkan π: πΈ πΊ β π(2) adalah suatu pelabelan sisi dimana π π£1 π£2 = 0 , π π£2 π£3 = β2 , π π£3 π£4 = +3 , π π£4 π£5 = β3 dan π π£5 π£1 = +2 . Dari definisi pemetaan injektif, π adalah pemetaan injektif. Misalkan π β : π πΊ β π(1) adalah suatu pelabelan titik, sedemikian sehingga didefinisikan π β π£1 = π π£1 π£2 + π π£5 π£1 = +2 , π β π£2 = π π£1 π£2 + π π£2 π£3 = β2, π β π£3 = π π£2 π£3 + π π£3 π£4 = +1, π β π£4 = π π£3 π£4 + π π£4 π£5 = 0 dan π β π£5 = π π£4 π£5 + π π£5 π£6 = β1. Dari definisi pemetaan surjektif, π β adalah pemetaan surjektif. Oleh karena itu, graf πΆ5 adalah graf π(2) π(1) β super graceful-sisi dan pelabelannya dapat dilihat pada Gambar berikut, v1 +2 2 v5
0
-1
-2
-3
-2
0 v4
v2
+1 3
v3
3. PELABELAN πΈ(π) π·(π) β SUPER GRACEFUL-SISI PADA πΈπ DAN πΈπ Teorema 3.1 [2] Graf kubus hiper π1 dan π2 bukan adalah (π, π) β ππΊπ untuk setiap bilangan asli π dan π. Bukti : a) Pada graf kubus hiper π1 (π π1 , πΈ π1 ) misalkan π π1 = π£1 , π£2 dan πΈ π1 = π£1 π£2 maka π = π π1 = 2 dan π = πΈ π1 = 1. Misalkan π dan π bilangan asli, maka dari (3.3) dan (3.4) diperoleh π(π) = {0} dan
31
b)
π π = {Β±π} . Akan dibuktikan bahwa graf kubus hiper π1 adalah bukan graf (π, π) β ππΊπ. Misalkan π: πΈ π1 β π(π) adalah pelabelan sisi dimana untuk setiap π π£1 π£2 = 0 , sehingga π: πΈ π1 β π(π) adalah pemetaan injektif. Misalkan π β : π π1 β π(π) adalah suatu pelabelan sisi, menurut Definisi 3.1.2 diperoleh, π β π£1 = π π£2 π£1 = 0 dan π β π£2 = π π£1 π£2 = 0 . Karena 0 adalah bukan anggota himpunana π(π) sehingga π β : π π1 β π(π) adalah bukan pemetaan surjektif, dapat disimpulkan bahwa graf kubus hiper π1 bukan (π, π) β ππΊπ untuk setiap bilangan asli π dan π. Pada graf kubus hiper π2 π π2 , πΈ π2 misalkan π π2 = {π£1 , π£2 , π£3 , π£4 } dan πΈ π2 = {π£1 π£2 , π£2 π£3 , π£3 π£4 , π£4 π£1 } maka π = π π2 = 4 dan π = πΈ π2 = 4. Misalkan π dan π bilangan asli, maka dari (3.3) dan (3.4) diperoleh π(π) = {Β±π, Β±(π + 1)} dan π π = {Β±π, Β±(π + 1)} . Akan dibuktikan bahwa graf kubus hiper π2 adalah bukan graf (π, π) β ππΊπ . Misalkan π: πΈ π2 β π(π) adalah pelabelan sisi dimana untuk setiap π π£1 π£2 = β(π + 1) , π π£2 π£3 = +(π + 1) , π π£3 π£4 = βπ dan π π£4 π£1 = +π, sehingga π: πΈ π2 β π(π)adalah pemetaan injektif. Misalkan π β : π πΊ β π(π) adalah pelabelan titik, sehingga diperoleh π β π£1 = π π£1 π£2 + π π£4 π£1 = β1 , π β π£2 = π π£1 π£2 + π π£2 π£3 = 0 , π β π£3 = π π£2 π£3 + π π£3 π£4 = +1 dan π β π£4 = π π£3 π£4 + π π£4 π£1 = 0 . Pelabelan tersebut dapat dilihat pada gambar berikut , v1
-(a+1)
-1
v2 0
+a
a+1
0
v4
-a
+1
v3
Karena 0 dan Β±1 adalah bukan anggota himpunan π(π) sehingga π β : π πΊ β π(π) adalah bukan pemetaan surjektif. Dengan kata lain, dua sisi yang berlabel +π dan β π tidak dapat bersisian pada setiap titik. Sehingga sisi yang berlabel +π dan β π harus disjoint satu dengan yang lainnya, sehingga menurut Definisi 3.1.2 diperoleh π β (π1 ) = β1, π β (π2 ) = β(2π + 1), π β (π3 ) = +(2π + 1) dan π β (π4 ) = +1. Karena Β±1 dan Β±(2π + 1) adalah bukan anggota himpunan π(π) sehingga π β : π πΊ β π(π) adalah bukan pemetaan surjektif. Dengan demikian π2 bukan pelabelan (π, π) β ππΊπ. β 4. PELABELAN πΈ(π) π·(π) β SUPER GRACEFUL-SISI PADA πΈπ JIKA πβ₯π Lema 4. 1 [2]
32
Graf kubus hiper π3 adalah bukan graf (π, π) β ππΊπ jika π > π + 4. Bukti : Akan dibuktikan jika π > π + 4 maka graf kubus hiper π3 adalah bukan (π, π) β ππΊπ. Diketahui π > π + 4 dengan kata lain π β 4 > π, maka π β 4 = π + π + 1 β π + 5 adalah nilai label positif yang terkecil, sehingga graf kubus hiper π3 bukan graf (π, π) β ππΊπ jika π > π + 4. Lema 4.2 [2] Kubus hiper π3 adalah bukan graf (π + 4, π) β ππΊπ. Bukti : Pada graf kubus hiper π3 misalkan πΈ π3 = {π£1 π£2 , π£1 π£4 , π£1 π£5 , π£4 π£8 , π£5 π£8 , π£5 π£6 , π£6 π£2 , π£7 π£8 , π£7 π£6 , π£4 π£3 , π£2 π£3 , π£3 π£7 } dan π π3 = {π£1 , π£2 , π£3 , π£4 , π£5 , π£6 , π£7 , π£8 }, maka π = π π2 = 8 dan = πΈ π2 = 12 . Misalkan π = π + 4 dan π bilangan asli sehingga dari (3.3) dan (3.4) diperoleh π(π + 4) = {Β±(π + 4), β¦ , Β±(π + 9)} dan π π = {Β±π, Β± π + 1 , β¦ , Β± π + 3 . Akan dibuktikan bahwa graf kubus hiper π3 adalah bukan graf (π + 4, π) β ππΊπ . Misalkan π: πΈ π3 β π(π) adalah pelabelan sisi dan π β : π π3 β π(π) adalah pelabelan titik. Misalkan π β π£1 = π dan π β ( π£2 ) = π + 1 , menurut Definisi 3.1.2 diperoleh π β π£1 = π π£1 π£2 + π π£1 π£4 + π π£1 π£5 π = (π + 4) + (π + 5) + (β(π + 9)) β¦(3.5) β π π£2 = π π£1 π£2 + π π£2 π£6 + π π£2 π£3 Hanya ada dua kemungkinan untuk melabeli titik π£2 yaitu : π β ( π£2 ) = π + 1 = π + 4 + π + 5 + (β π + 8 ) β¦(3.6) π β ( π£2 ) = π + 1 = π + 4 + π + 6 + (β π + 9 ) β¦(3.7) Diketahui bahwa kombinasi (3.5) dan (3.6) tidak dapat terjadi bersamaan karena akan terbentuk sisi ganda berlabel π + 4 dan π + 5 sehingga π β : π π3 β π(π) adalah bukan pemetaan surjektif. Begitu pula (3.5) dan (3.7) tidak dapat terjadi bersamaan karena akan terbentuk sisi ganda berlabel π + 4 dan β π + 9 sehingga π β : π π3 β π(π) adalah bukan pemetaan surjektif. Sehingga dapat disimpulkan bahwa graf kubus hiper π3 bukan graf (π + 4, π) β ππΊπ. β Lema 4.3 [2] Kubus hiper π3 adalah bukan graf (π + 3, π) β ππΊπ. Definisi 4.4 [2] Sebuah pelabelan (π, π) β ππΊπ dikatakan seimbang jika jumlah dari label sisi β sisi positif dan negatif yang bersisian pada tiap β tiap titik berjumlah Β±1. Sebuah pelabelan (π, π) β ππΊπ dikatakan tidak seimbang jika terdapat sebuah titik yang bersisian dengan tiga sisi yang bertanda sama. Contoh 4.4 Dimisalkan graf kubus hiper π3 adalah graf (1,1) β ππΊπ dan pelabelannya dapat dilihat pada gambar berikut,
33
v1 -3
-4
-1
5
-4 v5 -2
v2
3 -2 v6 -6
-5
2 1 v4
1
-1
v7
v8 6 2
-3
4 4
3 v3
Berdasarkan Definisi 4.4, pada pelabelan diatas dapat dilihat bahwa jumlah dari sisi β sisi positif dan negatif yang bersisian pada tiap β tiap titik berjumlah Β±1 dan tidak ada sisi β sisi yang bersisian yang bertanda sama pada tiap β tiap titik. Oleh karena itu, pelabelan (1,1) β ππΊπ pada graf π3 dapat dikatakan seimbang. Lema 4.5 [2] Jika sebuah graf kubus berlaku pelabelan (π, π) β ππΊπ seimbang, juga (π + π, π + π) β ππΊπ untuk setiap bilangan cacah π.
maka berlaku
Teorema 4.6 [2] Untuk π β₯ π, kubus hiper π3 adalah graf (π, π) β ππΊπ jika hanya jika π = π, π = π + 1 dan π = π + 2. 5. PELABELAN πΈ(π) π·(π) β SUPER GRACEFUL-SISI PADA πΈπ JIKA π<π Teorema 5.1 [2] Graf kubus hiper π3 adalah graf (π, π) β ππΊπ untuk π β π = 1, π β π = 2, π β π = 3 dan π β π = 4. Teorema 5.2 [2] Jika π + 5 β€ π, maka berlaku pelabelan (π, π) β ππΊπ tidak seimbang. Bukti: Pada graf kubus hiper π3 misalkan πΈ π3 = {π£1 π£2 , π£1 π£4 , π£1 π£5 , π£4 π£8 , π£5 π£8 , π£5 π£6 , π£2 π£6 , π£7 π£8 , π£7 π£6 , π£4 π£3 , π£2 π£3 , π£3 π£7 } dan π π3 = {π£1 , π£2 , π£3 , π£4 , π£5 , π£6, π£7 , π£8 } , maka π = π π3 = 8 dan π = πΈ π3 = 12 . Misalkan π dan π bilangan asli, maka dari (3.3) dan (3.4) diperoleh π π = Β±π, β¦ , Β±(π + 5) dan π π = {Β±π, β¦ , Β± π + 3 }. Misalkan graf kubus hiper π3 adalah graf π, π β ππΊπ seimbang. Maka label titik positif seimbang yang terbesar dimisalkan π β π£1 = π + 9 . Sedemikian sehingga π + 3 β€ π + 9 maka π β€ π + 6 . Jika π = π + 6 , maka diperoleh π π = {Β±π, β¦ , Β± π + 9 } . Misalkan π β π£1 = π + 9 dan π β π£2 = π + 8 , menurut Definisi 3.1.2 diperoleh,
34
π β π£1 = π π£1 π£2 + π π£4 π£1 + π π£1 π£5 π+9 = π+5 + π+4 β π β π π£2 = π π£2 π£1 + π π£2 π£6 + π π£2 π£3 Hanya ada dua kemungkinan untuk melabeli titik π£2 yaitu π β ( π£2 ) = π + 8 = (π + 5) + (π + 4) β (π + 1) π β ( π£2 ) = π + 8 = (π + 5) + (π + 3) β π Dapat dilihat bahwa π β (π£1 ) dan titik π β ( π£2 ) tidak dapat terjadi bersamaan Sehingga diperoleh kontradiksi bahwa graf kubus hiper π3 bukan graf (π, π) β ππΊπ seimbang. Jika π = π + 5, maka diperoleh π π = {Β±π, β¦ , Β± π + 8 }. Misalkan π β π£1 = π + 8 dan π β ( π£2 ) = π + 7 , menurut Definisi 3.1.2 diperoleh, π β π£1 = π π£1 π£2 + π π£1 π£4 + π π£1 π£5 π β π£2 = π π£1 π£2 + π π£2 π£6 + π π£2 π£3 Hanya ada tiga kemungkinan kombinasi untuk melabeli titik π£1 dan π£2 yaitu, π β ( π£1 ) = π + 8 = (π + 5) + (π + 4) β (π + 1) π β π£2 = π + 7 = (π + 5) + (π + 2) β π π β ( π£1 ) = π + 8 = (π + 4) + (π + 5) β (π + 1) π β π£2 = π + 7 = (π + 4) + (π + 3) β π π β ( π£1 ) = π + 8 = (π + 5) + (π + 3) β π π β π£2 = π + 7 = (π + 5) + (π + 4) β (π + 2) Untuk melabeli titik π β π£4 = π + 6 menurut Definisi 3.1.2 diperoleh, π β π£4 = π π£1 π£4 + π π£4 π£8 + π π£3 π£4 Hanya ada enam kemungkinan untuk melabeli titik π£4 yaitu, π β π£4 = π + 6 = (π + 4) + (π + 3) β (π + 1), π β π£4 = π + 6 = (π + 4) + (π + 2) β π, π β π£4 = π + 6 = (π + 5) + (π + 4) β (π + 3), π β π£4 = π + 6 = (π + 5) + (π + 3) β (π + 2), π β π£4 = π + 6 = (π + 5) + (π + 2) β (π + 1), π β π£4 = π + 6 = (π + 5) + (π + 1) β π, Dapat dilihat bahwa kombinasi π β ( π£1 ) , π β ( π£2 ) dan π β π£4 tidak dapat terjadi bersamaan karena akan terbentuk segitiga yang menghubungkan tiga titik yang berlabel π + 8 , π + 7 dan π + 6 , sehingga π β : π π3 β π(π) adalah bukan pemetaan surjektif. Dengan demikian diperoleh kontradiksi bahwa untuk π + 5 β€ π, setiap pelabelan (π, π) β ππΊπ harus tidak seimbang. β Lema 5.3 [2] Untuk setiap pelabelan (π, π) β ππΊπ pada graf kubus hiper π3 memuat paling banyak dua label titik positif tidak seimbang. Lema 5.4 [2] Jika π β (π’) β₯ π + 10, maka π’ harus tidak seimbang Teorema 5. 5 [2] Untuk π + 5 β€ π, jika graf kubus hiper π3 adalah graf (π, π) β ππΊπ maka πππ₯(π + 5,3π) β€ π β€ π + 8 dan π β€ 3.
35
Bukti: Untuk π + 5 β€ π, jika graf kubus hiper π3 adalah (π, π) β ππΊπ, maka πππ₯(π + 5,3π) β€ π β€ π + 8 dan π β€ 3. Pada graf kubus hiper π3 misalkan π π3 himpunan titik dan πΈ π3 himpunan sisi maka π = π π3 = 8 dan π = πΈ π3 = 12. Misalkan π dan π bilangan asli, dari (3.3) dan (3.4) maka diperoleh π π = Β±π, β¦ , Β±(π + 5) dan π π = {Β±π, β¦ , Β± π + 3 } . Misalkan graf kubus hiper π3 adalah (π, π) β ππΊπ , akan dibuktikan bahwa πππ₯(π + 5,3π) β€ π β€ π + 8 dan π β€ 3. Misalkan π + 5 β€ π maka menurut Lema 4.2, pelabelan (π, π) β ππΊπ pasti tidak seimbang. Menurut Lema 5.3 pelabelan (π, π) β ππΊπ graf kubus hiper π3 memuat paling banyak dua label titik positif tidak seimbang. Misalkan π’ dan π£ adalah titik β titik berlabel positif tidak seimbang pada pelabelan (π, π) β ππΊπ graf kubus hiper π3 , menurut Lema 5.4 maka π β (π’) = π + 10 dan π β (π’) = π + 11. Agar π(π) memuat kedua titik tersebut, π + 3 β€ π + 11 , dengan kata lain π β€ π + 8 . Misalkan π€ adalah label titik positif tidak seimbang terkecil. Diasumsikan bahwa π€ bersisian dengan tiga sisi berlabel positif. Maka menurut Definisi 3.1.2 diperoleh, π β (π€) = π + (π + 1) + (π + 2) = 3π + 3, sehingga dibutuhkan 3π + 3 β€ π + 3, dengan kata lain π β₯ 3π. Oleh karena itu, πππ₯(π + 5,3π) β€ π β€ π + 8 dimana tidak ada solusi untuk π β₯ 5 . Jika π = 4 , maka π = 12 sehingga dari (3.3) dan (3.4) diperoleh π 4 = Β±4, β¦ , Β±9 dan π 12 = {Β±12, β¦ , Β±15}. Label titik positif tidak seimbang terkecil yaitu 15 dan label titik positif terbesar seimbang yaitu 13. Meninggalkan 14 yang termuat pada π(12) dan tidak ada label titik yang seimbang atau tidak seimbang, yang masuk akal. Dapat disimpulkan bahwa π β€ 3. Oleh karena itu terbukti untuk π + 5 β€ π, jika graf kubus π3 adalah (π, π) β ππΊπ, maka πππ₯(π + 5,3π) β€ π β€ π + 8 dan π β€ 3. β Teorema 5.6 [2] Jika π β₯ 8 maka graf kubus hiper π3 adalah bukan graf (3, π) β ππΊπ. Teorema 5.7 [2] Untuk π β₯ 7, graf kubus hiper π3 adalah graf (2, π) β ππΊπ jika dan hanya jika π = 7 dan π = 9. Teorema 5. 8 [2] Untuk π β₯ 6, graf kubus hiper π3 adalah graf (1, π) β ππΊπ jika dan hanya jika π = 6 dan π = 7. Bukti : βΉ Untuk π β₯ 6, jika graf kubus hiper π3 adalah graf (1, π) β ππΊπ maka π = 6 dan π = 7. Lihat Definisi 3.1.2 untuk memperoleh π β : π π3 β π(6) , π β : π π3 β π(7) , π β : π π3 β π(8) dan π β : π π3 β π(9), sedemikian sehingga terbukti bahwa graf kubus hiper π3 adalah graf (1,6) β ππΊπ atau graf (1,7) β ππΊπ. βΈ Untuk π β₯ 6, jika π = 6 dan π = 7 maka graf kubus hiper π3 adalah graf (1, π) β ππΊπ .
36
Dengan mudah dapat dibuktikan bahwa graf kubus hiper π3 adalah graf (1,6) β ππΊπ atau graf (1,7) β ππΊπ, dan pelabelannya dapat dilihat pada gambar berikut v1 8
5 2
6
4
9 v5
-7 -6 v4
-6
v1
6
-9
7
-2
v7
v8 -4 -1
-5
-8 v5
-3
-5
-3
-6
10
-8
7
v3
v4
6
-7
-10 v6 1
-1
-9 -2
v2
-4
v6
3
1
v2
v7
v8 5 4
3
8 2
9 v3
Teorema Akibat 5.9 [2] Graf kubus hiper π3 merupakan graf (π, π) β ππΊπ jika π = 1 dan 1 β€ π β€ 7 , π = 2 dan 1 β€ π β€ 7 atau π = 9 serta π β₯ 3 dan π β 2 β€ π β€ π + 4. Bukti : Pada graf kubus hiper π3 misalkan πΈ π3 = {π£1 π£2 , π£1 π£4 , π£1 π£5 , π£4 π£8 , π£5 π£8 , π£5 π£6 , π£2 π£6 , π£7 π£8 , π£7 π£6 , π£4 π£3 , π£2 π£3 , π£3 π£7 } dan π π3 = π£1 , π£2 , π£3 , π£4 , π£5 , π£6, π£7 , π£8 maka π = π π3 = 8 dan π = πΈ π3 = 12 . Untuk π = 1, berdasarkan Teorema 3.3.6 graf kubus hiper π3 merupakan graf π, π β ππΊπ untuk π = 1, π = 2 dan π = 3, berdasarkan Teorema 5.1 graf kubus hiper π3 merupakan graf (π, π) β ππΊπ untuk π = 4 dan π = 5 serta berdasarkan Teorema 5.8 graf kubus hiper π3 merupakan graf (π, π) β ππΊπ untuk π = 6 dan π = 7. Untuk π = 2, berdasarkan Teorema 4.6 graf kubus hiper π3 merupakan graf (π, π) β ππΊπ untuk π = 1 dan π = 2, berdasarkan Teorema 5.1 graf kubus hiper π3 merupakan graf (π, π) β ππΊπ untuk π = 3 , π = 4, π = 5 dan π = 6 serta berdasarkan Teorema 5.7 graf kubus hiper π3 merupakan graf (π, π) β ππΊπ untuk π = 7 dan π = 9. Untuk π β₯ 3 , berdasarkan Teorema 4.5, Teorema 4.6 dan Teorema 5.1 graf kubus hiper π3 merupakan graf (π, π) β ππΊπ untuk π β 2 β€ π β€ π + 4. Oleh karena itu terbukti bahwa graf kubus hiper π3 merupakan graf (π, π) β ππΊπ jika π = 1 dan 1 β€ π β€ 7 , π = 2 dan 1 β€ π β€ 7 atau π = 9 serta π β₯ 3 dan π β 2 β€ π β€ π + 4. β
DAFTAR PUSTAKA [1]
[2]
37
Lestari. Triyas. 2010. βPelabelan Graceful dan Graceful Ganjil pada Graf Path, Graf Sikel, Gabungan Graf Sikel dan Graf Pathβ. Universitas Diponegoro. Semarang. Lee, S.M. and Harris Kwong. 2007. On Q(a) P(b)-super edge-gracefulness of Hypercubes, Journal of Combinatorial Mathematics and Combinatorial Computing (JCMCC) Volume 62. 25-34.
