PELABELAN AKAR RATA-RATA KUADRAT PADA GRAF LADDER DAN GRAF CORONA ⨀ 1,2,3
Azhar Mubarok1, Lucia Ratnasari2, Djuwandi3 Departemen Matematika, Fakultas Sains dan Matematika Universitas Diponegoro Semarang Jl.Prof. H.Soedarto,SH, Tembalang, Semarang
Abstract. A graph G with p vertices and q edges. A Root Square Mean Labeling of graph 2 is an injective function from the set of vertices 2 to the set {1,2, … , + 1} with edge is the number of side on the graph 2such that when each edges = AǴ is labeled by a function that defines as ceilling function or floor function from root square mean A and Ǵ, then the edge labels are distinct. For each of graphs 2 that uses root square mean labeling is called as Root Square Mean graph. In this paper, the study is about root square mean labeling on Ladder graph, Corona graph ⨀ . Then, we prove that ( ⨀ )∪ and ( , ⨀ ) graph are included as the root square mean graph. Keywords : Graph labeing, root square mean labeling, Ladder graph, Corona graph.
1. PENDAHULUAN Pelabelan graf sudah banyak dikaji mulai tahun 1960-an. Pelabelan pada suatu graf adalah suatu pemetaan (fungsi) yang memasangkan unsur-unsur graf (titik atau sisi) dengan bilangan (biasanya bilangan bulat). Jika domain dari pemetaan adalah himpunan titik, maka pelabelannya disebut pelabelan titik. Jika domainnya adalah sisi, maka pelabelannya disebut pelabelan sisi. Jika domainnya titik dan sisi, maka pelabelannya disebut pelabelan total [1]. Saat ini sudah mulai banyak jenis pelabelan graf yang dikembangkan. Salah satunya yaitu pelabelan rata-rata (mean labeling). Dalam artikel ini, penulis tertarik untuk membahas tentang pelabelan akar rata-rata kuadrat pada graf (Root Mean Square Labeling). Pelabelan akar rata-rata kuadrat diperkenalkan oleh [2]. Dalam artikel ini dibahas tentang pelabelan akar rata-rata kuadrat pada graf, yang terkait dengan graf path yaitu graf Ladder dan graf Corona ⨀ . Pengertian dan definisi-definisi yang berkaitan dengan graf menggunakan referensi [3].
2. HASIL DAN PEMBAHASAN Definisi 2.1 [2] Misalkan 2 adalah suatu graf dengan p banyaknya titik (vertice) dan q banyaknya sisi (edge). Pelabelan akar rata-rata kuadrat pada 2 adalah pemetaan injektif ∶ 2 → {1,2, … , + 1} sedemikian sehingga jika untuk setiap sisi = AǴ diberi label dengan AǴ = ( )
( )
( )
( )
atau
AǴ =
, maka menghasilkan label
sisi yang semuanya berbeda. Definisi 2.2 [4] Cartesian product dari dua graf 2 = ( , ) dan 2 = ( , ) dinotasikan 2 × 2 adalah graf dengan 2 ×2 = × dan dua titik A= ( ) dan Ǵ = adjacent di 2 × 2 jika ( = dan adjacent dengan ) atau ( = dan adjacent dengan ). Definisi 2.3 [5] Cartesian product dari × dinamakan graf Ladder dan dinotasikan dengan . Teorema 2.4 [5] Graf Ladder merupakan graf akar rata-rata kuadrat. Bukti : Didefinisikan fungsi ∶ → {1,2, … , + 1} dengan 65
Azhar Mubarok, Lucia Ratnasari dan Djuwandi (Pelabelan Akar Rata-rata Kuadrat pada Graf…)
Ǵ = 3 − 1, 1 ≤ ≤ , A = 3 − 2, 1 ≤ ≤ Selanjutnya diselidiki pelabelan sisi untuk graf dengan Definisi 2.1 sebagai berikut: AǴ
(3 − 2) + (3 − 1) 2
=
=
9
karena (3 − 2) < 9 − 9 + maka AǴ
=
(3 − 2) + (3 + 1) 2 9
karena (3 − 1) < 9 maka
ǴǴ
= =
Oleh karena 3 + 1 , maka ǴǴ
≤ 3 − 1 ,
= 3 − 2
=
AA
8
5 2
(3 − 2) + (3 − 1) 2
=
AA
− 9 +
=
− 3 +
− 3 +
5 2
8
≤ 3
,
(3 − 1) + (3 + 2) 2 + 3 +
(3 ) < 9
5 2
+ 3 +
(3 − 1) + (3 + 2) 2
=
8
≤
= 3 sedemikian sehingga setiap sisi diberi label dengan cara sebagai berikut : 66
(4 − 3) + (4 − 2) 2
13 2
16 − 20 +
Oleh karena (4 − 3) < 16 − 20 + 5 ≤ 4 − 2 , maka
= 3 − 1
9
=
=
(3 − 2) + (3 + 1) 2
=
AǴ = 3 − 2 1≤ ≤ AA = 3 − 1 1≤ ≤ − 1 ǴǴ = 3 1≤ ≤ − 1 Jadi, diperoleh himpunan hasil label sisi graf yaitu 2 = 1,2,3,4,5, … ,3 − 4,3 − 3,3 − 2 . n Definisi 2.5 [5] Graf corona 2 ⨀ 2 adalah graf yang dibentuk dengan mengambil dari satu graf 2 dengan n titik dan sebanyak salinan dari 2 dengan titik ke dari 2 adjacent ke setiap titik dalam salinan ke i dari 2 . Teorema 2.6 [5] Graf ⨀ merupakan graf akar rata-rata kuadrat. Bukti : Didefinisikan fungsi ∶ ⨀ → {1,2, … , + 1} dengan = 4 − 3, 1≤ ≤ = 4 − 2, 1≤ ≤ = 4 − 1, 1≤ ≤ Selanjutnya diselidiki pelabelan sisi untuk graf ⨀ dengan Definisi 2.1 sebagai berikut :
= Oleh Karena (4 − 1) ≤ 16 =
(4 − 4) + (4 − 2) 2 = 4 − 3
(4 − 3) + (4 + 1) 2
=
16
− 8 + 5
− 8 + 5< 4
, maka
(4 − 3) + (4 + 1) 2
= 4
Jurnal Matematika Vol. 19, No. 2, Agustus 2016 : 65 - 71
= Oleh karena 4 − 2 < 16 maka
(4 − 3) + (4 − 1) 2 = √16 − 16 + 5
− 16 + 5 ≤ 4 − 1 ,
=
(4 − 3) + (4 − 1) 2
=
(4 − 2) + (4 − 1) 2
Oleh karena (4 − 2) ≤ 16 maka =
)= { , , 5, , , , 5, , , , 5, , A , A , A5 , A , Ǵ , Ǵ , Ǵ5 , Ǵ }dan himpunan sisi (( ⨀ ) ∪ ) = { , , , 5 5, , 5, 5 , , , 5 5, , , , 5 5, , A A , A A5 , A5 A , A Ǵ , A Ǵ , A5 Ǵ5 , A Ǵ , Ǵ Ǵ , Ǵ Ǵ5 , Ǵ5 Ǵ } yang ditunjukkan pada Gambar 2.1.
= 4 − 2
=
16
− 12 +
8
5 − 12 + 2
< 4 − 1 ,
(4 − 2) + (4 − 1) 2
= 4 − 1 Sedemikian sehingga setiap sisi diberi label dengan cara sebagai berikut : = 4 − 3 1≤ ≤ = 4 − 2 1≤ ≤ = 4 − 1 1≤ ≤ = 4 1≤ ≤ − 1 Jadi, diperoleh himpunan hasil label sisi graf ⨀ yaitu 2 = 1,2,3, … ,4 − 4,4 − 3,4 − 2,4 − 1 . n
Definisi 2.7 [2] Union (gabungan) dari dua graf 2 dan 2 adalah 2 = 2 ∪ 2 , dimana himpunan titiknya = ∪ dan himpunan sisinya = ∪ Definisi 2.8 Diberikan graf ⨀ dan graf Ladder . Union dari kedua graf tersebut menghasilkan graf tidak terhubung. Hasil graf tersebut dinamakan graf ( ⨀ ) ∪ . Contoh 2.9 Dibeikan graf ( ⨀ ) ∪ dengan himpunan titik (( ⨀ ) ∪
Gambar 2.1 Graf ( ⨀
)∪
Teorema 2.10 Graf ( ⨀ )∪ merupakan graf akar rata-rata kuadrat. Bukti : Didefinisikan fungsi ∶ 2 → {1,2, … , + 1} dengan = 4 − 3, 1≤ ≤ = 4 − 2, 1≤ ≤ = 4 − 1, 1≤ ≤ A = 4 + 3 − 3, 1≤ ≤ Ǵ = 4 + 3 − 2, 1≤ ≤ Selanjutnya diselidiki pelabelan sisi untuk graf ( ⨀ ) ∪ dengan Definisi 2.1 sebagai berikut : =
(4 − 3) + (4 − 2) 2 =
16 − 20 +
Oleh karena (4 − 3) < 16 − 20 + maka = =
5
13 2
≤ 4 − 2 ,
(4 − 4) + (4 − 2) 2 = 4 − 3
(4 − 3) + (4 + 1) 2
=
16
− 8 + 5
67
Azhar Mubarok, Lucia Ratnasari dan Djuwandi (Pelabelan Akar Rata-rata Kuadrat pada Graf…)
Oleh karena (4 − 1) ≤ 16 =
=
(4 − 2) + (4 − 1) 2
Misalkan 4
=
=
=
16
− 12 +
8
5 − 12 + 2
= 4 − 1
+ 3 − 3) + (4 2 = 0, maka: =
+ 3)
(3 − 3) + (3 ) 2
=
− 9 +
9
− 9 +
9 2
≤ 3 − 1 ,
(4
= 4
(4
AǴ
=
= 3 − 2
+ 3 − 3) + (4 2
+ 3 − 2
=
(3 − 3) + (3 − 2) 2
=
=
9
− 15 + 5
− 15 +
13 2
≤ 3 − 2 ,
(3 − 3) + (3 − 2) 2 = 3 − 3
(4
+ 3 − 3) + (4 2
+ 3 − 2)
(4
+ 3 − 2) + (4 2
+ 3 + 1)
= 4 + 3 − 3 ǴǴ =
+ 3)
+ 3 − 2)
= 0, maka:
karena (3 − 3) < 9 maka
AǴ
(3 − 3) + (3 ) 2
+ 3 − 3) + (4 2
AǴ
< 4 − 1 ,
(4 − 2) + (4 − 1) 2
AǴ
=
AA
Misalkan 4
= 4 − 2
karena (3 − 2) < 9 maka 68
− 16 + 5 ≤ 4 − 1 ,
=
=
=
= √16 − 16 + 5
(4 − 3) + (4 − 1) 2
karena (4 − 2) ≤ 16 maka
(4
(4 − 3) + (4 + 1) 2
(4 − 3) + (4 − 1) 2
< 16
AA
AA
, maka
= 4
= karena 4 − 2 maka
− 8 + 5< 4
Misalkan 4 ǴǴ
=
= 0, maka:
(3 − 2) + (3 + 1) 2
=
9
karena (3 − 1) < 9 maka
− 3 +
− 3 +
5 2
8
≤ 3
,
Jurnal Matematika Vol. 19, No. 2, Agustus 2016 : 65 - 71
ǴǴ
=
ǴǴ
(4
=
(3 − 2) + (3 + 1) 2
=
− 1
+ 3 − 2) + (4 2
+ 3 + 1)
Bukti : Didefinisikan fungsi ∶ ( , ( ⨀ )) → {1,2, … , + 1} dengan A = 3 − 2, 1≤ ≤ , Ǵ = 3 − 1, 1≤ ≤ , = 3 + 4 − 4, 1≤ ≤ , = 3 + 4 − 3, 1≤ ≤ = 3 + 4 − 2, 1≤ ≤ , Selanjutnya diselidiki pelabelan sisi untuk graf ( ⨀ ) ∪ dengan Definisi 2.1 sebagai berikut :
= 4 + 3 − 1 sedemikian sehingga setiap sisi diberi label dengan cara sebagai berikut : = 4 − 3 1≤ ≤ , (3 − 2) + (3 − 1) = 4 − 2 1≤ ≤ , AǴ = = 4 − 1 1≤ ≤ , 2 = 4 1≤ ≤ − 1, AǴ = 4 + 3 − 3 1≤ ≤ , 5 = 9 − 9 + AA = 4 + 3 − 2 1 ≤ ≤ − 1, 2 ǴǴ = 4 + 3 − 1 1≤ ≤ − 1 karena Jadi, diperoleh himpunan hasil label sisi 8 graf ( ⨀ ) ∪ yaitu (3 − 2) < 9 − 9 + ≤ 3 − 1 , 2 = 1,2,3, … ,4 − 4,4 − maka 3,4 − 2,4 − 1,4 + 3 − 5,4 + (3 − 2) + (3 − 1) 3 − 4,4 + 3 − 3 . AǴ = 2 Definisi 2.11 Suatu graf Ladder dihubungkan dengan graf ( ⨀ ) = 3 − 2 dengan menambahkan satu garis di titik A pada graf Ladder dan titik pada (3 − 2) + (3 + 1) AA = graf ⨀ akan menghasilkan graf 2 terhubung. Hasil graf tersebut dinamakan graf ( , ( ⨀ )). 5 Contoh 2.12 Diberikan graf = 9 − 3 + 2 ( 5 , ( 5 ⨀ )). dengan himpunan titik 8 ) = 5, ( 5⨀ karena (3 − 1) < 9 − 3 + ≤ 3 {A , A , A5 , Ǵ , Ǵ , Ǵ5 , , , 5 , , , 5 , , , 5 } maka dan himpunan sisi ) = 5, ( 5⨀ {A A , A A5 , A Ǵ , A Ǵ , A5 Ǵ5 , Ǵ Ǵ , Ǵ Ǵ5 , A5 , , (3 − 2) + (3 + 1) = , , 5 5, , , 5 5, , , 5 5A} A 5, 2 yang ditunjukkan pada Gambar 3.37. = 3 − 1 Gambar 2.2 Graf (
5, ( 5⨀
))
Teorema 2.13 Graf , ⨀ merupakan graf akar rata-rata kuadrat.
ǴǴ
karena (3 ) < 9
=
(3 − 1) + (3 + 2) 2
=
+ 3 +
9
8
+ 3 +
5 2
≤ 3 + 1 , maka 69
,
Azhar Mubarok, Lucia Ratnasari dan Djuwandi (Pelabelan Akar Rata-rata Kuadrat pada Graf…)
ǴǴ (3
=
(3 − 1) + (3 + 2) 2
=
= 3
+ 4 − 4) + (3 2
Misalkan 3
=
16
=
+ 4 − 4) + (3 2
Misalkan 3
+ 4 − 4) + (3 2 = 0, maka:
=
karena (4 − 2) ≤ 16 maka =
70
25 2
− 28 +
= 4 − 4
+ 4 − 4 (3
− 28 +
(4 − 4) + (4 − 3) 2
=
= 3
=
=
8
≤
=
− 16 + 8 < 4 − 1 ,
= 4 − 1
(4 − 4) + (4 − 2) 2 =
= 3
− 24 + 10
(4 − 4) + (4 − 2) 2 = 4 − 3
+ 4 − 4
+ 4 − 3
(3
16
− 24 + 10 ≤ 4 − 2 ,
= 3
+ 4 − 2)
= 0, maka:
maka
+ 4)
(4 − 4) + (4 ) 2
+ 4 − 4) + (3 2
(4 − 3) < 16
=
+ 4)
+ 4 − 1
karena
+ 4 − 3)
− 16 + 8
(3
+ 4 − 4) + (3 2
=
(4 − 4) + (4 ) 2 16
(3
Misalkan 3
(4 − 4) + (4 − 3) 2
karena (4 − 2) < 16 4 − 3 , maka
=
= 3
+ 4 − 3)
= 0, maka:
=
(3
=
+ 3 2
+ 4 − 2
+ 4 − 3) + (3 2
Misalkan 3
=
= 0, maka:
karena (4 − 3) ≤ 16 maka =
+ 4 − 2)
(4 − 3) + (4 − 2) 2 =
16
− 20 +
− 20 + 5
13 2
< 4 − 2 ,
(4 − 3) + (4 − 2) 2 = 4 − 2
Jurnal Matematika Vol. 19, No. 2, Agustus 2016 : 65 - 71
=
= 3 =
(3 A
+ 4 − 2 (3
Misalkan A = =
+ 4 − 3) + (3 2 − 2) + (3 2
+ 4 − 2)
+ 4.1 − 4)
= 3, maka didapat :
(3.3 − 2) + (3.3 + 4.1 − 4) 2 7 + 9 2
= 8,06 = 3.3 − 1 = 3 − 1 sedemikian sehingga setiap sisi diberi label dengan cara sebagai berikut : AǴ = 3 − 2 1≤ ≤ AA = 3 − 1 1≤ ≤ − 1 ǴǴ = 3 1≤ ≤ − 1 A = 3 − 1 = = 3 + 4 1≤ ≤ − 1 = 3 + 4 − 1 1≤ ≤ − 1 = 3 + 4 − 3 1≤ ≤ − 1 = 3 + 4 − 2 1≤ ≤ − 1 Jadi, diperoleh himpunan hasil label sisi graf ( , ( ⨀ ))yaitu 2 = 1,2,3, … ,3 − 4,3 − 3,3 − 2,3 − 1,3 + 4 − 5,3 + 4 − 4,3 + 4 − 3,3 + 4 − 2 .
3. PENUTUP Berdasarkan hasil pembahasan, maka pelabelan akar rata-rata kuadrat dapat disimpulkan bahwa Ladder . graf ⨀ merupakan graf akar rata-rata kuadrat. Demikian juga graf ( ⨀ ) ∪ , graf ( , ⨀ ) merupakan graf akar rata-rata kuadrat. 4. DAFTAR PUSTAKA [1] Gallian, J.A., (2012), A Dynamic Survey of Graph Labeling, The Electronic Journal of Combinatories, 17. [2] Sandhya S., S., Somasundaram S., Anusa S., (2014), Root Square Mean Labeling of Graphs, International Journal of Contemporary Mathematical Sciences, 9(14): 667676. [3] Wilson, J. Robin, John J. Watkins, (1990), Graphs An Introductory Approach, NewYork : University Course Graphs, Network, and Design [4] Sandhya S. S, Somasundaram. S, Anusa S, (2014), Some New Results on Root Square Mean Labeling, International Journal of Mathematical Archive-5 (12) : 130-135. [5] Sandhya S. S, Somasundaram S, Anusa S., (2015), Root Square Mean Labeling of Some More Disconnected Graphs, International Mathematical Forum, 10(1) : 25-34.
71
