OTAL VERTEX IRREGULARITY STRENGTH PADA GRAF LINTASAN, GRAF SIKEL, GRAF STAR, GRAF PRISMA, DAN GRAF GABUNGAN DUA PRISMA

Abstract

Pelabelan total pada suatu graf G merupakan pemberian nilai (biasanya bilangan bulat positif) pada himpunan titik dan sisi. Salah satu jenis dari pelabelan total adalah pelabelan total titik irregular. Pelabelan total titik irregular merupakan pemberian nilai bilangan bulat positif (nilai yang dipakai boleh berulang) pada himpunan titik dan sisi dari suatu graf G, dengan bobot setiap titiknya berbeda. Untuk sebuah graf G terdapat beberapa variasi pelabelan total titik irregular. Dalam pelabelan graf, asalkan bobot setiap titiknya berbeda maka pelabelan tersebut dinamakan dengan pelabelan total titik irregular. Dalam karya tulis ilmiah ini penulis membahas tentang minimum label terbesar yang dipakai untuk melabeli suatu graf G dengan pelabelan total titik irregular yang disebut dengan total vertex irregularity strength suatu graf G, ( ) Gtvs . Tujuan dari penulisan karya tulis ilmiah ini adalah mendapatkan total vertex irregularity strength pada graf lintasan, graf sikel, graf star, graf prisma, dan graf gabungan dua prisma. Beberapa langkah yang diperlukan untuk mendapatkan ( ) Gtvs adalah melabeli graf G dengan pelabelan total titik irregular. Dalam melabeli graf tersebut kita selalu dapat menentukan bobot minimumnya yaitu pada titik yang berderajat paling kecil. Dengan demikian kemungkinan terkecil bobot maksimumnya juga dapat ditentukan dengan mengurutkan bobot mulai dari bobot minimum sampai ditemukan kemungkinan bobot maksimumnya. Bobot maksimum ini terletak pada titik yang berderat paling besar, guna memperkecil label yang digunakan. Jika graf tersebut mempunyai derajat terbesar ∆ , maka bobot maksimum yang diperoleh merupakan penjumlahan dari 1+∆ label. Selanjutnya minimum label terbesarnya dapat ditentukan, yaitu dengan membagi bobot maksimum dengan 1+∆ . Tetapi tidak semua minimum label terbesar dari suatu graf kita dapatkan dari bobot titik yang

maksimum, seperti pada graf star S . Misal diperoleh minimum label terbesarnya adalah k , kita dapat melabeli graf G secara total titik irregular dengan label n { } k,,2,1 K . Jika graf G dapat dilabeli, maka k merupakan ( ) Gtvs . Jika graf G tidak dapat dilabeli, nilai k diubah dengan menambahkan nilai 1 kemudian graf G dilabeli kembali. Kesimpulan yang diperoleh dari penelitian ini adalah untuk 2=n graf lintasan P n mempunyai ( ) 2= mempunyai ( ) ( ) Ctvs n =   + Ptvs 3 2n     n = Ptvs sedangkan untuk 3 ≥n graf lintasan P 3 1n   +     n . Untuk 3≥n graf sikel C dan untuk 3≥n graf star S Sedangkan untuk 3≥n graf prisma D gabungan dua prisma ( ) n n n mempunyai ( ) mempunyai ( ) D2 mempunyai ( ) = Dtvs 2 n Dtvs

Jurusan Matematika, Fakultas MIPA, Universitas Jember. n   + n 4 34     = .