Pelabelan Product Cordial Graf Gabungan pada Beberapa Graf Sikel dan Shadow Graph Sikel

Abstract

Abtrak

Misalkan graf G=V, E , Pelabelan product cordial adalah pelabelan titik biner f:EG→0, 1 yang menginduksi pelabelan sisi f*:EG→0, 1 dengan f*u,v=fu.fv, ∀u, v∈E(G) sehingga memenuhi syarat vf0-vf1≤1 dan ef0-ef1≤1 , dengan vf0,vf1,ef0,ef1 berturut – turut menyatakan banyaknya titik yang berlabel 0, banyaknya titik yang berlabel 1, banyaknya sisi yang berlabel 0 dan banyaknya sisi yang berlabel 1. Path gabungan dari graf G adalah graf yang diperoleh dengan menambahkan sisi antara Gi dan Gi+1 untuk i=1, 2, …, n-1 , dimana G1, G2, …, Gn, n≥2 dengan n salinan graf G. Shadow graph dari graf sikel dinotasikan dengan D2(Cn) adalah graf yang diperoleh dari dua graf sikel Cn' dan Cn" dengan menghubungkan setiap titik uij'∈Cn' dengan sebuah sisi ke titik yang adjacent dengan uij"∈Cn" (titik uij"∈Cn" adalah bayangan atau shadow dari uij'∈Cn' ). Dalam Tugas Akhir ini dibahas tentang pelabelan product cordial pada beberapa graf sikel serta shadow graph sikel.

Kata Kunci : pelabelan, cordial, sikel, biner, path, shadow graph.

1. PENDAHULUAN

Pelabelan graf merupakan suatu topik dalam teori graf. Objek kajiannya berupa graf yang secara umum direpresentasikan oleh titik dan sisi serta himpunan bagian bilangan asli yang disebut label. Pertama kali diperkenalkan oleh Sadlack (1964), kemudian Stewart (1966), Kotzig dan Rosa (1970). Hingga saat ini pemanfaatan teori pelabelan graf sangat dirasakan peranannya, terutama pada sektor sistem komunikasi dan transportasi, navigasi geografis, radar, penyimpanan data komputer, dan desain integrated circuit pada komponen elektronik. Graf merupakan pasangan himpunan titik dan himpunan sisi. Pengaitan titik-titik pada graf membentuk sisi dan dapat direpresentasikan pada gambar sehingga membentuk pola graf tertentu. Pola-pola yang terbentuk didefinisikan dan dikelompokkan menjadi kelas-kelas graf. Beberapa kelas graf menurut banyaknya sisi yang insiden terhadap titik antara lain graf reguler, yang derajat setiap titiknya adalah sama dan graf irreguler, yang derajat setiap titiknya ada yang tidak sama. Terdapat pula graf petersen yang diperumum yang merupakan salah satu subkelas graf reguler. Pelabelan merupakan pemetaan injektif yang memetakan unsur himpunan titik dan atau unsur himpunan sisi ke bilangan asli. Pelabelan titik adalah pelabelan dengan domain himpunan titik, pelabelan sisi adalah pelabelan dengan domain himpunan sisi, dan pelabelan total adalah pelabelan dengan doamin gabungan himpunan titik dan himpunan sisi