KETOTALSISIAJAIBAN GRAF DAN DEFISIENSINYA
DISERTASI Karya tulis sebagai salah satu syarat untuk memperoleh gelar Doktor dari Institut Teknologi Bandung
Oleh Anak Agung Gede Ngurah NIM: 30104006
Institut Teknologi Bandung 2007 i
KETOTALSISIAJAIBAN GRAF DAN DEFISIENSINYA
Oleh Anak Agung Gede Ngurah NIM: 30104006 (Program Studi Matematika)
Institut Teknologi Bandung
Menyetujui Tim Pembimbing
Tanggal: 26 November 2007 Ketua
(Prof. Dr. Edy Tri Baskoro)
Anggota
Anggota
(Dr. Rinovia Simanjuntak)
(Dr. Saladin Uttunggadewa)
ii
ABSTRAK KETOTALSISIAJAIBAN GRAF DAN DEFISIENSINYA Oleh Anak Agung Gede Ngurah NIM : 30104006 Pelabelan total sisi-ajaib pada suatu graf dengan p titik dan q sisi adalah suatu pemetaan satu-satu yang memetakan semua titik dan sisi ke {1, 2, 3, · · · , p + q} dengan sifat bahwa untuk setiap sisi pada graf tersebut jumlah label sisi dan label kedua titik ujungnya sama. Sejak diperkenalkan oleh Kotzig dan Rosa pada tahun 1970, pelabelan ini telah dikaji oleh banyak peneliti. Misalnya, Enomoto, Llado, Nakamigawa dan Ringel mengkaji pelabelan ini dengan memperkenalkan istilah pelabelan total sisi-ajaib super, yaitu pelabelan total sisi-ajaib yang mempunyai sifat bahwa semua titik mendapat p label terkecil. Di samping itu perluasan dan variasi dari pelabelan ini telah diperkenalkan. Aplikasinya pun mulai dikaji, seperti aplikasi dalam kriptografi yang menggunakan pelabelan total sisi-ajaib dalam konstruksi skema pembagian rahasia. Studi mengenai pelabelan total sisi-ajaib (super) yang banyak mendapat perhatian adalah klasifikasi graf yang memiliki pelabelan tersebut. Beberapa kelas graf telah diketahui mempunyai pelabelan tersebut. Namun banyak permasalahan yang sampai kini belum terpecahkan. Di antaranya adalah konjektur yang menyatakan bahwa semua graf pohon memiliki pelabelan total sisi-ajaib (super). Termotivasi oleh konjektur tersebut beberapa peneliti mengkaji pelabelan ini secara khusus pada graf pohon. Selain itu, beberapa kelas graf juga sudah dibuktikan tidak mempunyai kedua pelabelan tersebut. Berkaitan dengan hal tersebut diperkenalkan konsep defisiensi sisi-ajaib (super) dari suatu graf. Konsep ini menyatakan seberapa “dekat” suatu graf dengan suatu graf yang mempunyai pelabelan total sisi-ajaib (super). Disertasi ini mengkaji dua permasalahan yaitu studi klasifikasi graf yang mempunyai pelabelan total sisi-ajaib (super) dan studi penentuan defisiensi total sisiajaib (super) dari beberapa kelas graf. Untuk masalah pertama, kami mengkaji ketotalsisiajaiban beberapa graf, yakni pohon-seperti-lintasan (path-like-tree), graf kembang api (fire cracker ), graf lobster, dan graf rantai (chain graph). Di samping itu kami juga menyajikan metode konstruksi graf total sisi-ajaib (super) baru dari graf yang sudah diketahui total sisi-ajaib (super). Berdasarkan metode ini dihasilkan beberapa kelas graf total sisi-ajaib (super) baru. Beberapa di antaranya memberi dukungan atas kebenaran konjektur bahwa setiap graf pohon mempunyai pelabelan total sisi-ajaib (super). Sedangkan untuk masalah kedua, kami melakukan studi nilai defisiensi graf khususnya pada graf rantai, kipas, kipas ganda, roda, bipartit tak terhubung dan multipartit. Kata kunci : pelabelan graf, pelabelan total sisi-ajaib, pelabelan total sisi-ajaib super, defisiensi sisi-ajaib super.
iii
ABSTRACT The Edge-Magicness of Graphs and Its Deficiencies By Anak Agung Gede Ngurah NIM : 30104006 An edge-magic total labeling on a graph with p vertices and q edges is a one-toone map taking the vertices and edges onto the integers 1, 2, 3, · · · , p + q with the property that for each edge the sum of the label on the edge and the labels of its endpoints is constant. Since its introduction by Kotzig and Rosa in 1970, this labeling becomes one of the most famous graph labelings that have been studied by many researchers. Enomoto, Llado, Nakamigawa and Ringel studied this labeling by introducing the terminology of the super edge-magic total labeling, namely an edge-magic total labeling with an additional property that all vertices receive the p smallest labels. On the other hand, the extension and variation of these labelings have been introduced. Their applications have also been studied, such as in cryptography where edge-magic total labelings are used in a construction of a secret sharing scheme. The classification of graphs that admit a (super) edge-magic total labeling is an interesting topic for researchers. Some classes of graphs had been proved admitting these labeling. However, there still remain many open problems such as the conjectures which state that every tree admits an edge-magic total labeling and every tree admits a super edge-magic total labeling. Motivated by these conjectures, some researchers studied these labelings for particular types of trees. Additionally, some classes of graphs had been proved not admitting these labelings. Concerning to this fact, the concepts (super) edge-magic deficiencies of a graph were introduced. These concepts measure how “close” a graph with a (super) edge-magic graph is. In this dissertation, we study and give partial solutions to these two problems, namely classification of graphs that admit a (super) edge-magic total labeling and determination of (super) edge-magic deficiency of some classes of graphs. For the first problem, we consider (super) edge-magic total labeling for some classes of graphs such as path-like-trees, fire crackers, lobsters, and chain graphs. Also, we propose methods to construct new (super) edge-magic graphs from old ones. From these methods we can obtain new classes of (super) edge-magic graphs; some of the resulting graphs support the correctness of the conjectures that every tree has a (super) edge-magic total labeling. For the second problem, we study the deficiencies of particular type of graphs such as chain graphs, fans, double fans, wheels, disconnected bipartite graphs, and multipartite graphs. Keywords: graph labeling, edge-magic total labeling, super edge-magic total labeling, super edge-magic deficiency.
iv
PEDOMAN PENGGUNAAN DISERTASI
Disertasi Doktor yang tidak dipublikasikan terdaftar dan tersedia di Perpustakaan Institut Teknologi Bandung, dan terbuka untuk umum dengan ketentuan bahwa hak cipta ada pada pengarang dengan mengikuti aturan HaKI yang berlaku di Institut Teknologi Bandung. Referensi kepustakaan diperkenankan dicatat, tetapi pengutipan atau peringkasan hanya dapat dilakukan seizin pengarang dan harus disertai dengan kebiasaan ilmiah untuk menyebutkan sumbernya.
Memperbanyak atau menerbitkan sebagian atau seluruh disertasi haruslah seizin Direktur Program Pascasarjana, Institut Teknologi Bandung.
v
UCAPAN TERIMA KASIH
Puji syukur kehadirat Tuhan penulis panjatkan atas semua karunia-Nya.
Penulis ingin mengucapkan terima kasih kepada mereka yang sudah membantu selama menempuh pendidikan S3 di Program Studi Matematika ITB.
Kepada Tim Pembimbing; Prof. Dr. Edy Tri Baskoro, Dr. Rinovia Simanjuntak, dan Dr. Saladin Uttunggadewa atas kepercayaan, motivasi dan kesabarannya.
Kepada Tim Pembaca; Prof. Ketut Budayasa, Dr. Hilda Assiyatun, dan Dr. Achmad Muchlis atas koreksi dan masukan yang sangat bermanfaat.
Kepada Departemen Pendidikan Nasional Republik Indonesia atas bantuan Beasiswa Program Pascasarjana (BPPS).
Kepada Universitas Merdeka Malang atas ijin dan bantuannya.
Kepada semua keluarga, khususnya Bapak dan Ibu, atas doanya.
Kepada teman-teman di SSG Bandung dan Malang atas doanya, dan teman-teman S3 atas kerjasamanya.
Kepada F. A. Muntaner-Batle (Tony) atas paper, disertasi dan diskusinya.
Bandung, November 2007 Penulis
Anak Agung Gede Ngurah
vi
DAFTAR ISI
ABSTRAK
iii
ABSTRACT
iv
PEDOMAN PENGGUNAAN DISERTASI
v
UCAPAN TERIMA KASIH
vi
DAFTAR GAMBAR
ix
DAFTAR LAMBANG
xi
I
Pendahuluan
1
I.1
Latar belakang masalah . . . . . . . . . . . . . . . . . . . . . . . . .
1
I.2
Tujuan penelitian dan rumusan masalah . . . . . . . . . . . . . . . .
3
I.3
Hasil-hasil penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
I.4
Sistematika penulisan disertasi . . . . . . . . . . . . . . . . . . . . . .
4
II Graf dan Operasi graf
6
II.1 Graf dan subgraf . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
II.2 Klasifikasi graf
9
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
II.3 Operasi pada graf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 III Pelabelan Total Sisi-Ajaib (Super)
14
III.1 Sejarah pelabelan graf . . . . . . . . . . . . . . . . . . . . . . . . . . 14 III.2 Pelabelan total sisi-ajaib . . . . . . . . . . . . . . . . . . . . . . . . . 16 III.3 Pelabelan total sisi-ajaib super . . . . . . . . . . . . . . . . . . . . . . 19 III.4 Pelabelan ajaib (super) dari beberapa kelas graf . . . . . . . . . . . . 25 III.4.1 Pelabelan ajaib super pada graf pohon-seperti-lintasan . . . . 26 III.4.2 Pelabelan ajaib super pada graf subdivisi dari graf bintang K1,3 30 III.4.3 Pelabelan ajaib super pada graf lobster . . . . . . . . . . . . . 37 III.4.4 Pelabelan ajaib pada graf rantai . . . . . . . . . . . . . . . . . 44
vii
IV Graf Ajaib (Super) dengan Sisi Pendan
54
IV.1 Graf ajaib dengan sisi pendan . . . . . . . . . . . . . . . . . . . . . . 55 IV.2 Graf ajaib super dengan sisi pendan . . . . . . . . . . . . . . . . . . . 63 V Defisiensi Sisi-Ajaib Super
73
V.1 Defisiensi ajaib super dari graf rantai . . . . . . . . . . . . . . . . . . 77 V.2 Defisiensi ajaib super dari graf kipas, kipas ganda dan roda . . . . . . 80 V.3 Defisiensi ajaib super dari graf bipartit dan multipartit lengkap . . . 87 VI Kesimpulan dan Masalah Terbuka
95
DAFTAR PUSTAKA
97
DAFTAR RIWAYAT HIDUP
102
viii
DAFTAR GAMBAR
II.1
Ketetanggaan pada graf dan graf 3-reguler . . . . . . . . . . . . .
7
II.2
Graf yang isomorfik dan tidak isomorfik . . . . . . . . . . . . . .
7
II.3
Graf dan subgrafnya . . . . . . . . . . . . . . . . . . . . . . . . .
7
II.4
Graf G dan G + uv . . . . . . . . . . . . . . . . . . . . . . . . . .
8
II.5
Graf dengan 4 komponen
. . . . . . . . . . . . . . . . . . . . . .
8
II.6
Graf dengan 5 blok . . . . . . . . . . . . . . . . . . . . . . . . . .
9
II.7
Graf lengkap K6 dan graf bipartit lengkap K3,4 . . . . . . . . . .
9
II.8
Graf Petersen diperumum . . . . . . . . . . . . . . . . . . . . . . 10
II.9
Graf pohon, graf hutan, dan graf siklus-tunggal . . . . . . . . . . 10
II.10
Beberapa graf tanpa siklus . . . . . . . . . . . . . . . . . . . . . . 11
II.11
Graf yang dihasilkan dari operasi join . . . . . . . . . . . . . . . . 12
II.12
Graf yang dihasilkan dari operasi perkalian . . . . . . . . . . . . . 12
II.13
Graf yang dihasilkan dari operasi corona . . . . . . . . . . . . . . 13
III.1
Pelabelan ajaib pada graf C4 dan pelabelan dualnya
III.2
Pelabelan ajaib super pada suatu graf dan pelabelan dualnya . . 22
III.3
Graf P22 dipandang sebagai subgraf dari graf grid . . . . . . . . . 26
III.4
Pohon-seperti-lintasan . . . . . . . . . . . . . . . . . . . . . . . . 27
III.5
Pelabelan titik pada P22 dan pohon-seperti-lintasan yang menun-
. . . . . . . 17
jukkan bahwa f (u0 ) + f (v 0 ) = f (u) + f (v) . . . . . . . . . . . . . 29 III.6
Graf pohon T (4, 5, 7) . . . . . . . . . . . . . . . . . . . . . . . . . 30
III.7
Pelabelan titik dari T (4, 6, 9). . . . . . . . . . . . . . . . . . . . . 34
III.8
Pelabelan titik dari T (3, 6, 10) . . . . . . . . . . . . . . . . . . . . 36
III.9
Pelabelan titik dari graf kembang api . . . . . . . . . . . . . . . . 40
III.10
Graf lobster dengan struktur tertentu . . . . . . . . . . . . . . . . 41
III.11
Pelabelan titik dari graf lobster yang mempunyai struktur seperti graf lobster pada Gambar III.10. . . . . . . . . . . . . . . . . . . 44
III.12
Pembentukkan 3C4 -lintasan dari 2C4 -lintasan . . . . . . . . . . . 45
III.13
Pelabelan ajaib pada kC4 -lintasan . . . . . . . . . . . . . . . . . . 52
ix
IV.1
1 (a) pelabelan titik dari P5,2 dan graf yang dihasilkan dengan me4 nerapkan Teorema IV.1, (b) pelabelan titik dari P6,1 dan graf
yang dihasilkan dengan menerapkan Teorema IV.1. . . . . . . . . 58 IV.2
Graf H dan pelabelan titiknya. . . . . . . . . . . . . . . . . . . . 59
IV.3
Pelabelan titik dari H. . . . . . . . . . . . . . . . . . . . . . . . . 60
IV.4
6 Pelabelan titik dari P5,1 , dan graf yang dihasilkan dengan mene-
rapkan Teorema IV.3 . . . . . . . . . . . . . . . . . . . . . . . . . 63 IV.5
Graf G dan pelabelan titiknya. . . . . . . . . . . . . . . . . . . . 63
IV.6
Pelabelan titik dari graf L5,1 dan P6 ∪ K1,2 yang memenuhi Teorema IV.4 dan graf yang dihasilkan dengan menerapkan Teorema IV.4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
IV.7
Graf ajaib super P8 ∪ K1,3 dan graf yang dihasilkan dengan menerapkan Teorema IV.5. . . . . . . . . . . . . . . . . . . . . . . . 68
IV.8
Graf ajaib super K1,8 ∪ K1,3 dan graf yang dihasilkan dengan menerapkan Teorema IV.6. . . . . . . . . . . . . . . . . . . . . . . 69
IV.9
Pelabelan titik pada graf P (9, 3). . . . . . . . . . . . . . . . . . . 70
IV.10
Graf ajaib super K1,8 dan graf yang dihasilkan dengan menerapkan Teorema IV.8. . . . . . . . . . . . . . . . . . . . . . . . . . . 72
V.1
Pelabelan titik dari 5K4 − lintasan ∪ K1 . . . . . . . . . . . . . . 80
V.2
Pelabelan titik dari F10,2 ∪ 4K1 . . . . . . . . . . . . . . . . . . . . 84
V.3
Pelabelan titik dari 3K2,2 dan 4K2,2 . . . . . . . . . . . . . . . . . 89
V.4
Pelabelan titik dari K4,4 ∪ K5,5 ∪ K6,6 . . . . . . . . . . . . . . . . 92
x
DAFTAR LAMBANG
LAMBANG
Nama
Pemakaian pertama kali pada hal.
V (G)
Himpunan titik dari graf G
6
E(G)
Himpunan sisi dari graf G
6
N (u)
Himpunan semua tetangga titik u
6
dG (v)
Derajat dari titik v pada graf G
6
δ(G)
Derajat minimum dari graf G
6
∆(G)
Derajat maksimum dari graf G
6
G∼ =H
Graf G isomorfik dengan graf H
6
H⊆G
H adalah subgraf dari graf G
7
G−u
Subgraf dari graf G dengan V (G − u) = V (G) \ {u} dan E(G − u) = E(G) \ {uv|uv ∈ E(G)}
G−e
7
Subgraf dari graf G dengan V (G − e) = V (G) dan E(G − e) = E(G) \ {e}
G + uv
7
Suatu graf dengan himpunan titik V (G) dan V (G + uv) = E(G) + {uv} dan
7
W
Jalan
8
Pn
Graf lintasan dengan n titik
8
d(u, v)
Jarak antara titik u dan v
8
k(G)
Banyaknya komponen pada graf G
8
Kn
Graf lengkap dengan n titik
9
Kn,m
Graf bipartit lengkap yang setiap himpunan partitnya berturut-turut terdiri dari n dan m titik
9
P (n, m)
Graf Petersen diperumum dengan 2n titik
9
Dn
Graf prisma dengan 2n titik
10
Cn
Graf siklus dengan n titik
10
xi
LAMBANG
Nama
Pemakaian pertama kali pada hal.
G1 ∪ G2
Graf gabungan dari G1 dan G2
11
nH
Gabungan saling asing n buah graf H
11
G1 + G2
Graf join dari G1 dan G2
11
Wn
Graf roda dengan n + 1 titik
11
C3t
Graf pertemanan
11
Fn
Graf kipas dengan n + 1 titik
12
Fn,2
Graf kipas ganda dengan n + 2 titik
12
G1 × G2
Graf hasil kali dari G1 dan G2
12
Bn
Graf buku dengan n halaman
12
Cn × Pm
Graf prisma diperumum
12
Ln
Graf tangga dengan 2n titik
12
G H
Graf corona dari G dan H
12
Gk
Pangkat k dari graf lintasan G
22
T (m, n, k)
Subdivisi dari graf K1,3
30
F C(m1 , m2 , · · · , mn )
Graf kembang api yang dibentuk dari graf bintang K1,m1 +1 , K1,m2 +1 , · · · , K1,mn +1 m ,mn+1
L(l1m1 ,m2 , l2m2 ,m3 , · · · , l1 n
)
Lobster yang mempunyai struktur seperti pada Gambar III.10
kF − lintasan
41
Graf rantai dengan k blok dimana setiap bloknya adalah graf F
1 P2k+1,m
37
45
Caterpillar yang dibentuk dengan menambahkan m sisi pendan, dengan m genap, ke setiap titik dari graf lintasan P2k+1 , k ≥ 1
xii
57
LAMBANG
Nama
Pemakaian pertama kali pada hal.
2 P2k,m
Caterpillar yang dibentuk dengan menambahkan m − 1 sisi pendan ke satu titik dari graf lintasan P2 dan m sisi pendan ke titik yang lain dari P2k , k ≥ 1
3 P2k+1,m
57
Caterpillar yang dibentuk dengan menambahkan m sisi pendan ke setiap titik dari P2k+1 , k ≥ 1, kecuali satu titik yang berderajat satu
4 Pn,1
57
Caterpillar yang dibentuk dengan menambahkan satu sisi pendan ke n − 1 titik dari Pn , n ≥ 2
T P2k+1
Pohon-seperti-lintasan dengan jumlah titik ganjil
5 P2k,m
57
57
Caterpillar yang dibentuk dengan menambahkan m ≥ 1 sisi pendan ke setiap titik dari P2k , k ≥ 1
6 P2k+1,1
62
Caterpillar yang dibentuk dengan menambahkan satu sisi pendan ke setiap titik P2k+1 , k ≥ 1
7 P2k+1,m
62
Caterpillar yang dibentuk dengan menambahkan satu sisi pendan ke satu titik berderajat satu dan m ≥ 1 sisi pendan ke titik yang lain dari P2k+1 , k ≥ 1
T P2k
Pohon-seperti-lintasan dengan jumlah titik genap
L∗2k
62
62
Graf pohon yang dihasilkan dengan menerapkan Teorema IV.3 pada graf P2k
xiii
62
LAMBANG
Nama
Pemakaian pertama kali pada hal.
L5∗ 2k,m
Graf pohon yang dihasilkan dengan 5 menerapkan Teorema IV.3 pada graf P2k,m
L6∗ 2k+1,1
Graf pohon yang dihasilkan dengan 6 menerapkan Teorema IV.3 pada graf P2k+1,1
L7∗ 2k+1,m
62
Graf pohon yang dihasilkan dengan T menerapkan Teorema IV.3 pada graf P2k
L2n+1,1
62
Graf pohon yang dihasilkan dengan 7 menerapkan Teorema IV.3 pada graf P2k+1,m
T∗ P2k
62
62
Lobster yang diperoleh dengan menambahkan sebuah titik pendan ke setiap titik berderajat 1 dari P2n+1 K1
L2n,1
65
Lobster yang diperoleh dengan menambahkan sebuah titik pendan ke setiap titik berderajat 1 dari P2n K1 kecuali titik pendan paling kiri atau kanan
Sn,n+1
65
Graf bintang ganda yang diperoleh dengan menghubungkan center dari dua buah graf bintang K1,n dan K1,n+1
L12k+1,m
Graf pohon yang dihasilkan dengan 1 menerapkan Teorema IV.4 pada graf P2k+1,m
L22k,m
65
Graf pohon yang dihasilkan dengan 3 menerapkan Teorema IV.4 pada graf P2k+1,m
L4n,m
65
Graf pohon yang dihasilkan dengan 2 menerapkan Teorema IV.4 pada graf P2k,m
L32k+1,m
65
65
Graf pohon yang dihasilkan dengan 4 menerapkan Teorema IV.4 pada graf Pn,m
xiv
65
LAMBANG
Nama
Pemakaian pertama kali pada hal.
T T2k+1
Graf pohon yang dihasilkan dengan T menerapkan Teorema IV.4 pada graf P2k+1
T2n+1,1
Graf pohon yang dihasilkan dengan menerapkan Teorema IV.4 pada graf L2n+1,1
T2n,1
65
Graf pohon yang dihasilkan dengan menerapkan Teorema IV.4 pada graf L2n,1
Ln,n+1
65
65
Graf pohon yang dihasilkan dengan menerapkan Teorema IV.4 pada graf Sn,n+1
65
µ(G)
Defisiensi sisi-ajaib dari graf G
73
Fp
Bilangan Fibonacci ke-p
73
µs (G)
Defisiensi sisi-ajaib super dari graf G
73
xv
