PELABELAN L(2,1) PADA OPERASI BEBERAPA KELAS GRAF

JIMT Vol. 13 No. 2 Desember 2016 (Hal 73 - 84) Jurnal Ilmiah Matematika dan Terapan ISSN : 2450 – 766X

PELABELAN L(2,1) PADA OPERASI BEBERAPA KELAS GRAF S. Fatimah1, I W. Sudarsana2, dan S. Musdalifah3 1,2,3

Program Studi Matematika Jurusan Matematika

Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Tadulako Jalan Sukarno-Hatta Km. 9 Palu 94118, Indonesia [email protected], [email protected], [email protected]

ABSTRACT Let G be a graph with p vertices dan q edges. An L(2,1) labeling of graph G is a function𝑓: 𝑉 → {0,1,2 ⋯ , 𝑘} such that statisfies the conditions|𝑓(𝑢) − 𝑓(𝑣)| ≥ 2, for𝑑(𝑢, 𝑣) = 1 for|𝑓(𝑢) − 𝑓(𝑣)| ≥ 1, if 𝑑(𝑢, 𝑣) = 2. A number k is called the span of L(2,1) labeling, if k is the largest label vertex of it’s labeling. Notation 𝜆(𝐺) states that the smallest span of all L(2,1) labelings in a graph G. L’(2,1) labeling on injectiveL(2,1) labeling. A minimum span of all labeling L’(2,1) denoted by 𝜆′(𝐺). A graph G which has L’(2,1) labeling is called the graph L’(2.1). The results showed that fan graph (𝐹𝑛 ) with 𝜆′ (𝐹𝑛 ) = 𝑛 + 1, wheel graph (𝑊𝑛 ) with 𝜆′ (𝑊𝑛 ) = 𝑛 + 1, lotus graph (𝑇𝑛 ) with 𝜆′ (𝑇𝑛 ) = 2𝑛 + 2, 𝐾1 ⨀(𝑃𝑛 ⋃𝐹𝑛 ) graph with 𝜆′ (𝐾1 ⨀(𝑃𝑛 ⋃𝐹𝑛 )) = 2𝑛 + 2 and 𝐾1 ⨀𝑡𝐶𝑛 graph with 𝜆′ (𝐾1 ⨀𝑡𝐶𝑛 ) = 𝑡𝑛 + 1 is graph L’(2,1). Keywords

: Fan Graph, Lotus Graph, L(2,1) labeling, L’(2,1) labeling, Wheel Graph.

ABSTRAK Misalkan G adalah graf dengan p titik dan q sisi. Pelabelan L(2,1) pada graf G adalah fungsi 𝑓: 𝑉 → {0,1,2 ⋯ , 𝑘} yang memenuhi kondisi |𝑓(𝑢) − 𝑓(𝑣)| ≥ 2, jika 𝑑(𝑢, 𝑣) = 1 dan |𝑓(𝑢) − 𝑓(𝑣)| ≥ 1, jika 𝑑(𝑢, 𝑣) = 2. Bilangan k disebut span dari pelabelan L(2,1), jika k adalah label titik terbesar dari pelabelan L(2,1). Notasi 𝜆(𝐺) menyatakan span terkecil atas semua pelabelan L(2,1) pada graf G. Pelabelan L(2,1) yang injektif disebut pelabelan L’(2,1). Minimum span atas semua pelabelan L’(2,1) dinotasikan dengan𝜆′(𝐺). Sebuah graf G yang mempunyai pelabelan L’(2,1) dinamakan graf L’(2,1). Dalam penilitian ini, telah berhasil ditunjukkan bahwa graf kipas (𝐹𝑛 ) dengan 𝜆′ (𝐹𝑛 ) = 𝑛 + 1, graf roda (𝑊𝑛 ) dengan 𝜆′ (𝑊𝑛 ) = 𝑛 + 1, graf teratai (𝑇𝑛 ) dengan 𝜆′ (𝑇𝑛 ) = 2𝑛 + 2, graf 𝐾1 ⨀(𝑃𝑛 ⋃𝐹𝑛 ) dengan 𝜆′ (𝐾1 ⨀(𝑃𝑛 ⋃𝐹𝑛 )) = 2𝑛 + 2 dan graf 𝐾1 ⨀𝑡𝐶𝑛 dengan 𝜆′ (𝐾1 ⨀𝑡𝐶𝑛 ) = 𝑡𝑛 + 1 adalah graf L’(2,1). Kata kunci

: Graf Kipas, Graf Roda, Graf Teratai, Pelabelan L(2,1), Pelabelan L’(2,1).

I.

PENDAHULUAN Ada banyak jenis pelabelan graf yang telah dikembangkan, diantaranya adalah pelabelan

gracefull, pelabelan harmoni, pelabelan super mean, pelabelan ajaib, pelabelan anti ajaib, pelabelan prime cordial, pelabelan triangular dan pelabelan L(2,1). Pelabelan L(2,1) didefinisikan sebagai pemberian label pada titik suatu graf dengan fungsi adalah fungsi 𝑓: 𝑉 → 𝑁 ∪ {0} sehingga mutlak dari selisih label dari dua titik yang bertetangga langsung paling sedikit dua dan mutlak dari dua titik yang berjarak dua selisih labelnya paling sedikit satu. 𝑓: 𝑉 → {0,1,2 ⋯ , 𝑘} dimana k adalah span dari pelabelan L(2,1). Span adalah label terbesar dari pelabelan L(2,1) pada graf G atau k ∈ 𝑓(𝑣) yang terbesar. Span dari suatu graf G bisa lebih dari satu. Minimum dari beberapa span graf G dilambangkan dengan 𝜆(𝐺). Secara matematis dapat ditulis 𝜆(𝐺) = min{𝑠𝑝𝑎𝑛 (𝐺) atas semua pelabelan L(2,1) yang dimiliki sebuah graf G}. Temuan terakhir terkait pelabelan L(2,1) adalah graf lintasan, graf siklus, graf bintang dan graf kincir [4]. Namun, untuk graf kipas, graf roda, graf teratai, graf 𝐾1 ⊙ (𝑃𝑛 ∪ 𝐹𝑛 ) dan graf 𝐾1 ⊙ 𝑡𝐶𝑛 masih menjadi masalah terbuka. II.

TINJAUAN PUSTAKA 2.1.

Definisi Graf Graf adalah suatu diagram yang terdiri dari titik-titik (points) yang disebut vertex (node /

titik) yang dihubungkan dengan garis yang dinamakan sisi dimana setiap sisi terhubung dengan tepat 2 vertex [5]. 2.2.

Jenis – Jenis Graf Graf dibagi menjadi beberapa kelas, pada bagian ini ada beberapa jenis – jenis graf

yang berkaitan pada penelitian ini. 1.

Graf Lengkap

K1

K3

K2

K4

Gambar 1. Contoh graf lengkap 2.

Graf Lintasan e1 v1 P1

P2

e2

e1 v2

v1

v2

v3

P3

Gambar 2. Contoh graf lintasan

74

3.

Graf Siklus

C3

C5

Gambar 3. Contoh graf siklus 4.

Graf Bintang

Gambar 4. Contoh graf bintang 𝑆9 5.

Graf Kipas V1

V2

V3

Vn-1

Vn

V0

Gambar 5. Contoh graf kipas 𝐹𝑛 6.

Graf Roda

Gambar 6. Contoh graf roda 𝑊8 7.

Graf Teratai Graf teratai dibentuk dari graf lengkap 𝐾1 korona graf bintang 𝑆𝑛 kemudian titik 𝑛 − 1

pada graf bintang menghasilkan satu titik baru dan terhubung pada titik tengah graf bintang. Dengan demikian, graf teratai mempunyai 2𝑛 + 2 titik dan (2𝑛 + 1) sisi.

Gambar 7. Contoh graf teratai𝑛 = 6

75

8.

Graf 𝐾1 ⊙ (𝑃𝑛 ∪ 𝐹𝑛 ) Graf 𝐾1 ⊙ (𝑃𝑛 ∪ 𝐹𝑛 ) adalah graf yang dibentuk dari graf 𝐾1 korona graf lintasan 𝑃𝑛

gabung graf kipas 𝐹𝑛 yaitu = 𝐾1 ⊙ (𝑃𝑛 ∪ 𝐹𝑛 ), dengan demikian graf 𝐾1 ⊙ (𝑃𝑛 ∪ 𝐹𝑛 ) mempunyai (2𝑛 + 2) titik dan (4𝑛 + 1) sisi.

Gambar 8. Contoh graf 𝐾1 ⊙ (𝑃7 ∪ 𝐹7 ) 9.

Graf 𝐾1 ⊙ 𝑡𝐶𝑛 Graf 𝐾1 ⊙ 𝑡𝐶𝑛 adalah graf yang dibentuk dari graf 𝐾1 korona beberapa graf siklus 𝑡𝐶𝑛

yaitu 𝐾1 ⊙ 𝑡𝐶𝑛 , dengan demikian graf 𝐾1 ⊙ 𝑡𝐶𝑛 mempunyai (𝑡𝑛 + 1) titik dan (2𝑡𝑛) sisi.

Gambar 9: Contoh graf 𝐾1 ⊙ 4𝐶6

2.3.

Operasi Korona pada Graf Misalkan 𝐺1 dan 𝐺2 adalah dua buah graf sebarang. 𝐺1 korona 𝐺2 , (𝐺1 ⊙ 𝐺2 ) adalah

graf yang dibentuk dari graf 𝐺1 dan graf 𝐺2 dengan graf 𝐺2 sebanyak order 𝐺1 , (|𝐺1 |), sebut 𝐺21 , 𝐺2 2 ⋯ , 𝐺2 |𝐺1 | dengan cara menghubungkan semua titik di 𝐺2 (𝑖) ke satu titik 𝑥𝑖 di 𝐺1 , dengan 𝑖 = 1,2, ⋯ , |𝐺1 |.

76

Graf 𝐺1

Graf 𝐺2

Gambar 10. Contoh graf 𝐺1 ⊙ 𝐺2 2.4.

Pelabelan L(2,1) Pelabelan jarak dua, L(2,1) pada graf G dengan p titik dan q sisi adalah fungsi 𝑓: 𝑉 →

𝑁 ∪ {0}sedemikian sehingga memenuhi syarat : 1.

|𝑓(𝑢) − 𝑓(𝑣)| ≥ 2, jika 𝑑(𝑢, 𝑣) = 1

2.

|𝑓(𝑢) − 𝑓(𝑣)| ≥ 1, jika 𝑑(𝑢, 𝑣) = 2 𝑓: 𝑉 → {0,1,2 ⋯ , 𝑘} dimana k adalah span dari pelabelan L(2,1). Span adalah label

terbesar dari pelabelan L(2,1) pada graf G atau k ∈ 𝑓(𝑣) yang terbesar. Span dari suatu graf G bisa lebih dari satu. Minimal dari beberapa span graf G dilambangkan dengan 𝜆(𝐺) atau 𝜆(𝐺) = min{span(G)}. Proposisi 1 : Nilai 𝜆 dari sebuah graf bintang 𝐾1,∆ adalah ∆ + 1, dimana ∆ adalah derajat maksimum [3]. Proposisi 2 : 𝜆(𝐻) ≤ 𝜆(𝐺), untuk setiap subgraf H dari sebuah graf G [2]. III.

HASIL DAN PEMBAHASAN Pada bagian ini akan dibahas pelabelan L’(2,1)pada graf kipas (𝐹𝑛 ), graf roda (𝑊𝑛 ), graf teratai,

graf 𝐾1 ⨀(𝑃𝑛 ⋃𝐹𝑛 ) dan graf 𝐾1 ⨀𝑡𝐶𝑛 . Definisi 1: Pelabelan L(2,1) pada graf G adalah fungsi 𝑓: 𝑉 → {0,1,2 ⋯ , 𝑘} yang memenuhi kondisi (1) |𝑓(𝑢) − 𝑓(𝑣)| ≥ 2, jika 𝑑(𝑢, 𝑣) = 1, (2) |𝑓(𝑢) − 𝑓(𝑣)| ≥ 1, jika 𝑑(𝑢, 𝑣) = 2. Bilangan k disebut span dari pelabelan L(2,1), 𝑓, jika k adalah label titik terbesar atas pelabelan L(2,1), 𝑓 tersebut. Notasi 𝜆(𝐺) menunjukkan span terkecil atas semua pelabelan L(2,1) pada graf G.

77

7

0 5

6 4

2

2

4

6

5 0

7

Gambar 11. Contoh pelabelan L(2,1) pada graf 𝐷2 (𝐶5 ). Definisi 2: Pelabelan L(2,1) yang injektif disebut pelabelan L’(2,1) dan minimal span atas semua pelabelan L’(2,1) disebut 𝜆′(𝐺). 2

5

4

0

1

3

6

Gambar 12. Contoh pelabelan L’(2,1) pada graf 𝑇(𝑃4 ) 3.1.

Graf Kipas 𝑭𝒏 Sebelum itu akan diberikan notasi titik dan sisi dari graf kipas (𝐹𝑛 ) untuk 𝑛 ≥ 1 adalah

sebagai berikut : V1

V2

V3 V0 V4

V5

Vn

Gambar 13. Penotasian titik pada graf 𝐹𝑛 Berdasarkan Gambar 13 di atas dapat dinotasikan himpunan titik dan sisi pada graf 𝐹𝑛 untuk 𝑛 ≥ 1, yaitu : 𝑉(𝐹𝑛 ) = {𝑣𝑖 |0 ≤ 𝑖 ≤ 𝑛} 𝐸(𝐹𝑛 ) = {𝑒𝑖 |1 ≤ 𝑖 ≤ 𝑛} dengan 𝑒𝑖 = 𝑣0 𝑣𝑖 ; 0 ≤ 𝑖 ≤ 𝑛. Teorema 1 : Graf Kipas dengan 𝑛 + 1 titik, 𝐹𝑛 , mepunyai𝜆′(𝐹𝑛 ) = 𝑛 + 1

78

Bukti : Pandang notasi titik dan sisi untuk graf 𝐹𝑛 pada gambar 13 akan ditunjukkan 𝜆′(𝐹𝑛 ) ≤ 𝑛 + 1 yaitu dengan mengkonstruksi pelabelan L’(2,1) dari graf 𝐹𝑛 dengan span 𝑛 + 1. Definisikan fungsi injektif𝑓: 𝑉(𝐹𝑛 ) → {0,1, … , 𝑛 + 1} sebagai berikut: Untuk n ganjil: 𝑓(𝑣0 ) = 0 𝑓(𝑣𝑖 ) = 2𝑖

𝑛

; 𝑖 = 1,2, … , ⌊ ⌋ 2

𝑓 (𝑣⌈𝑛⌉ ) = 𝑛 + 1 2

𝑛

𝑓(𝑣𝑖 ) = 2𝑖 − 5

; 𝑖 = ⌈ ⌉ + 1, … , 𝑛

Untuk n genap: 𝑓(𝑣0 ) = 0 𝑓(𝑣𝑖 ) = 2𝑖

; 𝑖 = 1,2, … ,

2

𝑛

𝑓(𝑣𝑖 ) = 2𝑖 − 5 𝑓(𝑣𝑛 ) = 𝑛 + 1

𝑛 2

; 𝑖 = + 1, … , 𝑛 − 1 2

Dapat diverifikasi bahwa fungsi 𝑓 memenuhi sifat pelabelan L(2,1) dalam Definisi 1 dan Definisi 2 dengan label terbesar adalah 𝑛 + 1. Oleh karena itu, 𝜆′(𝐹𝑛 ) ≤ 𝑛 + 1. Selanjutnya akan ditunjukkan 𝜆′(𝐹𝑛 ) ≥ 𝑛 + 1. Pandang graf 𝐾1,𝑛 adalah subgraf dari 𝐹𝑛 dan menurut Proposisi 1 dan 2, memberikan𝜆′(𝐹𝑛 ) ≥ 𝜆′(𝐾1,𝑛 ) = 𝑛 + 1 sehingga 𝜆′(𝐹𝑛 ) ≥ 𝑛 + 1 . Jadi, 𝜆′(𝐹𝑛 ) = 𝑛 + 1. 3.2.

Graf Roda 𝑾𝒏 Sebelum itu akan diberikan notasi titik secara umum pada graf roda (𝑊𝑛 ) untuk 𝑛 ≥ 1

adalah sebagai berikut : V1

Vn

V2

V0 V5

V3

V4

Gambar 14. Penotasian titik pada graf 𝑊𝑛 Berdasarkan Gambar 14 di atas dapat dinotasikan himpunan titik pada graf 𝑊𝑛 untuk 𝑛 ≥ 1, yaitu : 𝑉(𝑊𝑛 ) = {𝑣𝑖 |0 ≤ 𝑖 ≤ 𝑛} 𝐸(𝑊𝑛 ) = {𝑒𝑖 |1 ≤ 𝑖 ≤ 𝑛} dengan 𝑒𝑖 = 𝑣0 𝑣𝑖 ; 0 ≤ 𝑖 ≤ 𝑛.

79

Teorema 2 : Graf Roda dengan 𝑛 + 1 titik, 𝑊𝑛 , mepunyai𝜆′(𝑊𝑛 ) = 𝑛 + 1 Bukti : Pandang notasi titik dan sisi untuk graf 𝑊𝑛 pada gambar 14 akan ditunjukkan 𝜆′(𝑊𝑛 ) ≤ 𝑛 + 1 yaitu dengan mengkonstruksi pelabelan L’(2,1) dari graf 𝑊𝑛 dengan span 𝑛 + 1. Definisikan fungsi injektif𝑓: 𝑉(𝑊𝑛 ) → {0,1, … , 𝑛 + 1} sebagai berikut : Untuk n ganjil: 𝑓(𝑣0 ) = 0 𝑓(𝑣𝑖 ) = 2𝑖

𝑛

; 𝑖 = 1,2, … , ⌊ ⌋ 2

𝑓 (𝑣⌈𝑛⌉ ) = 𝑛 + 1 2

𝑛

𝑓(𝑣𝑖 ) = 2𝑖 − 5

; 𝑖 = ⌈ ⌉ + 1, … , 𝑛

Untuk n genap: 𝑓(𝑣0 ) = 0 𝑓(𝑣𝑖 ) = 2𝑖

; 𝑖 = 1,2, … ,

2

𝑛

𝑓(𝑣𝑖 ) = 2𝑖 − 5 𝑓(𝑣𝑛 ) = 𝑛 + 1

𝑛 2

; 𝑖 = + 1, … , 𝑛 − 1 2

Dapat di verifikasi bahwa fungsi 𝑓 memenuhi sifat pelabelan L(2,1) dalam Definisi 1 dan Definisi 2 dengan label terbesar adalah 𝑛 + 1. Oleh karena itu, 𝜆′(𝑊𝑛 ) ≤ 𝑛 + 1. Selanjutnya akan ditunjukkan 𝜆′(𝑊𝑛 ) ≥ 𝑛 + 1. Pandang graf 𝐾1,𝑛 adalah subgraf dari 𝑊𝑛 dan menurut Proposisi 1 dan 2, memberikan 𝜆′(𝑊𝑛 ) ≥ 𝜆′(𝐾1,𝑛 ) = 𝑛 + 1 sehingga 𝜆′(𝑊𝑛 ) ≥ 𝑛 + 1 . Jadi, 𝜆′(𝑊𝑛 ) = 𝑛 + 1. 3.3.

Graf Teratai 𝑻𝒏 Sebelum itu akan diberikan notasi titik dan sisi dari graf teratai (𝑇𝑛 ) untuk 𝑛 ≥ 1 adalah

sebagai berikut : v’1

v’2

v1

v’3

v2

v3

v’n

vn

v0

v’0

Gambar 15. Penotasian titik pada graf 𝑇𝑛

80

Berdasarkan Gambar 15 dapat dinotasikan himpunan titik pada graf 𝑇𝑛 untuk 𝑛 ≥ 1, yaitu : 𝑉(𝑇𝑛 ) = {𝑣𝑖 |0 ≤ 𝑖 ≤ 𝑛} ∪ {𝑣 , 𝑖 |0 ≤ 𝑖 ≤ 𝑛} 𝐸(𝑇𝑛 ) = {𝑒𝑖 |1 ≤ 𝑖 ≤ 𝑛} dengan 𝑒𝑖 = 𝑣0 𝑣′𝑖 ; 0 ≤ 𝑖 ≤ 𝑛. Teorema 3 : Graf Teratai dengan 2𝑛 + 2 titik, 𝑇𝑛 , mepunyai𝜆′(𝑇𝑛 ) = 2𝑛 + 2 Bukti : Pandang notasi titik dan sisi untuk graf 𝑇𝑛 pada gambar 15 akan ditunjukkan 𝜆′(𝑇𝑛 ) ≤ 2𝑛 + 2 yaitu dengan mengkonstruksi pelabelan L’(2,1) dari graf 𝑇𝑛 dengan span 2𝑛 + 2. Definisikan fungsi injektif𝑓: 𝑉(𝑇𝑛 ) → {0,1, … ,2𝑛 + 2} sebagai berikut : 𝑓(𝑣0 ) = 0 𝑓(𝑣𝑖 ) = 𝑖 + 1 𝑓(𝑣 ′ 0 ) = 2𝑛 + 2 𝑓(𝑣 ′ 𝑖 ) = 𝑖 + 𝑛 + 1

; 𝑖 = 1,2, … , 𝑛 ; 𝑖 = 1,2, … , 𝑛

Dapat diverifikasi bahwa fungsi 𝑓 memenuhi sifat pelabelan L(2,1) dalam Definisi 1 dan Definisi 2 dengan label terbesar adalah 2𝑛 + 2. Oleh karena itu, 𝜆′(𝑇𝑛 ) ≤ 2𝑛 + 2. Selanjutnya akan ditunjukkan 𝜆′(𝑇𝑛 ) ≥ 2𝑛 + 2. Pandang graf 𝐾1,2𝑛+1 adalah subgraf dari 𝑇𝑛 dan menurut Proposisi 1 dan 2, memberikan 𝜆′(𝑇𝑛 ) ≥ 𝜆′(𝐾1,2𝑛+1 ) = 2𝑛 + 2 sehingga 𝜆′(𝑇𝑛 ) ≥ 2𝑛 + 2. Jadi, 𝜆′(𝑇𝑛 ) = 2𝑛 + 2. 3.4.

Graf 𝑲𝟏 ⨀(𝑷𝒏 ⋃𝑭𝒏 ) Sebelum itu akan diberikan notasi titik dan sisi dari graf 𝐾1 ⨀(𝑃𝑛 ∪ 𝐹𝑛 ) untuk 𝑛 ≥ 1 adalah

sebagai berikut : v1

v2

v3

vn

v’3

v’n

v0

v’1

v’2

v’0

Gambar 16. Penotasian titik pada graf 𝐾1 ⨀(𝑃𝑛 ∪ 𝐹𝑛 )

81

Berdasarkan Gambar 16 di atas dapat dinotasikan himpunan titik pada graf 𝐾1 ⨀(𝑃𝑛 ∪ 𝐹𝑛 ) untuk 𝑛 ≥ 1, yaitu : 𝑉(𝐾1 ⨀(𝑃𝑛 ∪ 𝐹𝑛 )) = {𝑣𝑖 |0 ≤ 𝑖 ≤ 𝑛} ∪ {𝑣 , 𝑖 |0 ≤ 𝑖 ≤ 𝑛} 𝐸(𝑇𝑛 ) = {𝑒𝑖 |1 ≤ 𝑖 ≤ 𝑛} dengan 𝑒𝑖 = 𝑣0 𝑣′𝑖 ; 0 ≤ 𝑖 ≤ 𝑛. Teorema 4 : Graf 𝐾1 ⨀(𝑃𝑛 ∪ 𝐹𝑛 ) dengan 2𝑛 + 2 titik, 𝐾1 ⨀(𝑃𝑛 ∪ 𝐹𝑛 ), mepunyai 𝜆′(𝐾1 ⨀(𝑃𝑛 ∪ 𝐹𝑛 )) = 2𝑛 + 2 Bukti : Pandang notasi titik dan sisi untuk graf 𝐾1 ⨀(𝑃𝑛 ∪ 𝐹𝑛 ) pada gambar 16 akan ditunjukkan 𝜆′(𝐾1 ⨀(𝑃𝑛 ∪ 𝐹𝑛 )) ≤ 2𝑛 + 2 yaitu dengan mengkonstruksi pelabelan L’(2,1) dari graf 𝐾1 ⨀(𝑃𝑛 ∪ 𝐹𝑛 ) dengan span 2𝑛 + 2. Masukkan fungsi injektif𝑓: 𝑉(𝐾1 ⨀(𝑃𝑛 ∪ 𝐹𝑛 )) → {0,1, … ,2𝑛 + 2} sebagai berikut: 𝑓(𝑣0 ) = 0 𝑓(𝑣𝑖 ) = 2𝑖 + 1 𝑓(𝑣 ′ 0 ) = 2 𝑓(𝑣 ′ 𝑖 ) = 2𝑖 + 2 𝑓(𝑣𝑛 ) = 2𝑛 + 2

; 𝑖 = 1,2, … , 𝑛 ; 𝑖 = 1,2, … , 𝑛 − 1

Dapat diverifikasi bahwa fungsi 𝑓 memenuhi sifat pelabelan L(2,1) dalam Definisi 1 dan Definisi 2 dengan label terbesar adalah 2𝑛 + 2. Oleh karena itu, 𝜆′(𝐾1 ⨀(𝑃𝑛 ∪ 𝐹𝑛 )) ≤ 2𝑛 + 2. Selanjutnya akan ditunjukkan 𝜆′(𝐾1 ⨀(𝑃𝑛 ∪ 𝐹𝑛 )) ≥ 2𝑛 + 2. Pandang graf 𝐾1,2𝑛+1 adalah subgraf dari 𝐾1 ⨀(𝑃𝑛 ∪ 𝐹𝑛 ) dan menurut Proposisi 1 dan 2, memberikan 𝜆′(𝐾1 ⨀(𝑃𝑛 ∪ 𝐹𝑛 )) ≥ 𝜆′(𝐾1,2𝑛+1 ) = 2𝑛 + 2 sehingga 𝜆′(𝐾1 ⨀(𝑃𝑛 ∪ 𝐹𝑛 )) ≥ 2𝑛 + 2. Jadi, 𝜆′(𝐾1 ⨀(𝑃𝑛 ∪ 𝐹𝑛 )) = 2𝑛 + 2. 3.5.

Graf 𝑲𝟏 ⨀𝒕𝑪𝒏 Sebelum itu akan diberikan notasi titik dan sisi dari graf 𝐾1 ⨀𝑡𝐶𝑛 untuk 𝑛 ≥ 1 dan 𝑡 ≥ 1

adalah sebagai berikut : v jn

v21 v j1

v2n

v1n

v11

v1 vj 5

vn

v2

v22

v0

v15

v12 v25

v5

v3 v4 v j2

v14

v13

v23

v j4

v24

v j3

Gambar 17. Penotasian titik pada graf 𝐾1 ⨀𝑡𝐶𝑛

82

Berdasarkan Gambar 17 di atas dapat dinotasikan himpunan titik pada graf 𝐾1 ⨀𝑡𝐶𝑛 untuk 𝑛 ≥ 1 dan 𝑡 ≥ 1, yaitu : 𝑗

𝑉(𝐾1 ⨀𝑡𝐶𝑛 ) = {𝑣0 , 𝑣𝑖 |0 ≤ 𝑖 ≤ 𝑛 𝑑𝑎𝑛 0 ≤ 𝑗 ≤ 𝑡 − 1} 𝑗

𝐸(𝐾1 ⨀𝑡𝐶𝑛 ) = {𝑒𝑖 |1 ≤ 𝑖 ≤ 𝑛} dengan 𝑒𝑖 = 𝑣0 𝑣𝑖 ; 0 ≤ 𝑖 ≤ 𝑛. Teorema 5 : Graf 𝐾1 ⨀𝑡𝐶𝑛 dengan 𝑡𝑛 + 1 titik, 𝐾1 ⨀𝑡𝐶𝑛 mempunyai𝜆′(𝐾1 ⨀𝑡𝐶𝑛 ) = 𝑡𝑛 + 1 Bukti : Pandang notasi titik dan sisi untuk graf 𝐾1 ⨀(𝑃𝑛 ∪ 𝐹𝑛 ) pada gambar 17 akan ditunjukkan 𝜆′(𝐾1 ⨀𝑡𝐶𝑛 ) ≤ 𝑡𝑛 + 1 yaitu dengan mengkonstruksi pelabelan L’(2,1) dari graf 𝐾1 ⨀𝑡𝐶𝑛 dengan span 𝑡𝑛 + 1. Masukkan fungsi injektif𝑓: 𝑉(𝑇𝑛 ) → {0,1, … , 𝑡𝑛 + 1} sebagai berikut : Untuk n ganjil: 𝑓(𝑣0 ) = 0 𝑓(𝑣𝑖 ) = 2𝑖

; 𝑖 = 1,2, … , ⌈ ⌉

𝑓(𝑣𝑖 ) = 2𝑖 − 𝑛

; 𝑖 = ⌈ ⌉ + 1, … , 𝑛

𝑗

𝑓(𝑣𝑖 ) = 𝑓(𝑣𝑖 ) + 𝑗𝑛

𝑛

𝑛

2

2

; 𝑖 = 1,2, … , 𝑛 dan 𝑗 = 1,2, … , 𝑡

𝑓 (𝑣 𝑡𝑛 ) = 𝑡𝑛 + 1 ⌈ ⌉ 2

Untuk n genap: 𝑓(𝑣0 ) = 0 𝑓(𝑣𝑖 ) = 2𝑖

; 𝑖 = 1,2, … ,

𝑓(𝑣𝑖 ) = 2𝑖 − 𝑛 + 1

; 𝑖 = + 1, … , 𝑛

𝑗

𝑓(𝑣𝑖 ) = 𝑓(𝑣𝑖 ) + 𝑗𝑛 𝑓(𝑣𝑛𝑡 ) = 𝑡𝑛 + 1

𝑛

𝑛 2

2

; 𝑖 = 1,2, … , 𝑛 dan 𝑗 = 1,2, … , 𝑡

Dapat diverifikasi bahwa fungsi 𝑓 memenuhi sifat pelabelan L(2,1) dalam Definisi 1 dan Definisi 2 dengan label terbesar adalah 𝑡𝑛 + 1. Oleh karena itu, 𝜆′(𝐾1 ⨀𝑡𝐶𝑛 ) ≤ 𝑡𝑛 + 1. Selanjutnya akan ditunjukkan 𝜆′(𝐾1 ⨀𝑡𝐶𝑛 ) ≥ 𝑡𝑛 + 1. Pandang graf 𝐾1,𝑡𝑛 adalah subgraf dari 𝐾1 ⨀𝑡𝐶𝑛 dan menurut Proposisi 1 dan 2, memberikan 𝜆′(𝐾1 ⨀𝑡𝐶𝑛 ) ≥ 𝜆′(𝐾1,𝑡𝑛 ) = 2𝑛 + 2 sehingga 𝜆′(𝐾1 ⨀𝑡𝐶𝑛 ) ≥ 𝑡𝑛 + 1. Jadi, 𝜆′(𝐾1 ⨀𝑡𝐶𝑛 ) = 𝑡𝑛 + 1. IV.

KESIMPULAN Berdasarkan hasil penelitian yang telah dilakukan, dapat disimpulkan : 1.

Graf kipas 𝐹𝑛 adalah L’(2,1) dengan 𝑛 ≥ 5 , 𝜆′(𝐹𝑛 ) = 𝑛 + 1

2.

Graf roda 𝑊𝑛 adalah L’(2,1) dengan 𝑛 ≥ 5, 𝜆′(𝑊𝑛 ) = 𝑛 + 1

3.

Graf teratai 𝑇𝑛 adalah L’(2,1) dengan 𝑛 ≥ 3, 𝜆′(𝑇𝑛 ) = 2𝑛 + 2

4.

Graf 𝐾1 ⨀(𝑃𝑛 ∪ 𝐹𝑛 ) adalah L’(2,1) untuk 𝑛 ≥ 3, 𝜆′(𝐾1 ⨀(𝑃𝑛 ∪ 𝐹𝑛 )) = 2𝑛 + 2

5.

Graf 𝐾1 ⨀𝑡𝐶𝑛 adalah L’(2,1) untuk 𝑛 ≥ 5 dan 𝑡 ≥ 3, 𝜆′(𝐾1 ⨀𝑡𝐶𝑛 ) = 𝑡𝑛 + 1

83

DAFTAR PUSTAKA [1].

Didi, S. dan Nanang, P, 2008, Pengetahuan Dasar Teori Graph, Binadarma, , Palembang, 2.

[2].

G. Chang and D. Kuo, The L(2,1)-labelling problem on graphs, SIAM J. Discrete Math, 9(2), 1996, 309-316.

[3].

J. Griggs and R. Yeh, 1992, Labeling graph with a condition at distance 2, SIAM J. Discrete

Math, 5, 586-595. [4].

Vadya, S. K., Vihol, P. L., Dani, N. A., Bantva, D. D, 2011, Distance two labeling of some total

graph, Gen. Math. Notes, 3, 100-107. [5].

Wilson, R. J and Watkins, J.J, 1990, Graphs : An Introductory Approach a First Course in

Discrete Mathematics., John Willy and Sons, Inc, New York.

84