Kata kunci: pelabelan total, takreguler titik, graf Petersen.
Roswitha, Mania; Indriati, Diari; Kusmayadi, Tri Atmojo*)
Fakultas MIPA UNS, Penelitian, Dikti, Fundamental, 2006.
Diasumsikan G=(V,E) adalah graf berhingga, terhubung, sederhana dan tak berarah, dengan V adalah himpunan titik (vertex) dan E adalah himpunan sisi (edge). Graf G mempunyai v titik 
V dan e sisi E. Pelabelan pada graf (graph labeling) menurut Wallis [9] adalah fungsi bijeksi yang menghubungkan elemen-elemen graf dengan suatu himpunan bilangan bulat non negatif. Dalam hal ini, jika domain yang digunakan adalah himpunan titik, maka pelabelan disebut pelabelan titik (vertex labeling), jika domainnya adalah himpunan sisi, maka pelabelan disebut pelabelan sisi (edge labeling) dan jika domainnya adalah titik dan sisi maka pelabelan disebut sebagai pelabelan total (total labeling). Pelabelan juga dilakukan dengan cara menghubungkan jumlah label dengan elemen-elemen graf. Jumlah label ini dikenal sebagai bobot (weight) dari elemen graf. Oleh Wallis [9] didefinisikan bobot titik υ pada pelabelan total ∂ dari elemen-elemen graf G = (V, E) sebagai
wt(x) = ∂(x) ∑ ∂(xy)
xyE
dan bobot sisi xy sebagai
wt(xy) = ∂(x) ∂(xy) ∂(y).
Chartrand et al.[3] kemudian memperkenalkan pengertian kekuatan (strength) dari G, yaitu 5 (G), sebagai berikut. Diberikan label bilangan bulat positip pada sisi-sisi sebuah graf sederhana berorder paling tidak 3 dengan cara sedemikian sehingga graf menjadi takreguler, yaitu, bobot (jumlah label) pada tiap titik berbeda. Nilai minimum dari label terbesar dari semua penetapan takregular kemudian dikenal sebagai kekuatan takreguler (irregularity strength) dari graf G, atau s(G).
<span style=”color: black” casino lang=”FI”>Beberapa penelitian dari Dimitz et al. [4], Fandre dan Lehel [7] membahas tentang s(G) ini pada kelas graf sederhana, survei pada tree yang dapat dilihat pada makalah Bohman dan Kravitz [2]. Termotivasi oleh penelitian-penelitian tersebut, Baca et al.[1]memperkenalkan kekuatan takreguler total titik (total vertex irregularity strength) dari graf G, dinotasikan dengan tvs(G), sebagai nilai minimum dari label terbesar pada penetapan takregular terhadap titik-titik graf G. Baca et al.[1] membuktikan bahwa untuk tree T dengan n titik berderajad 1 (n pendant vertices) dan tidak terdapat titik berderajad 2, berlaku 
≤ tυѕ (T) ≤ n. Untuk graf G dengan derajad minimum δ dan derajad maksimum Δ berlaku 
≤ tυs(G) ≤ │υ│ Δ – 2δ 1. Baca et al. [1] juga membuktikan bahwa untuk cycle 
, tυѕ () = 
.
Hasil penelitian Baca et al. [1] yang lain adalah tvs(G) untuk graf bipartit (bipartite graph)
, tυs
= 
dan untuk graf lengkap Kn, berlaku tυs(Kn)=2 untuk semua n ≥ 2. Kemudian hasil ini ditindak-lanjuti oleh Wijaya [10] dengan mencari tυs(Km,n), kekuatan takregular titik total dari graf bipartit lengkap, yaitu tυs(Km,n)≥max
.
Dalam penelitian ini, peneliti menindak lanjuti hasil dari Baca et al.[1] dan Wijaya et al. [10] dengan mengkaji tυs dari kelas graf yang belum dibahas oleh keduanya, khususnya graf Petersen.
Metode yang digunakan adalah metode verifikasi algoritmik, yaitu pelabelan yang dihasilkan disajikan dalam bentuk algoritma secara umum dan pengujian kebenarannya disajikan dalam bentuk teoritis (lema atau teorema).
Untuk graf G=(V, E) dengan himpunan titik V dan himpunan sisi E didefinisikan pelabelan ∂, VUE→ {1,2,3,…,k} sebagai k-pelabelan titik total takreguler (vertex irregular total k-labeling) dari graf G jika untuk setiap 2 titik berbeda x dan y dari G terdapat wt(x)≠ wt(y).
Nilai k minimum dimana graf G mempunyai k-pelabelan total titik takreguler disebut kekuatan takreguler titik total, tυs(G).
Hasil penelitian adalah teorema tentang pelabelan takreguler titik total pada graf Petersen sebagai berikut :
Teorema 4.3.1:
Pandang Kn sebagai graf lengkap dengan setiap titiknya berderajad n-1, maka graf Kn merupakan graf (n-l)-reguler sehingga tυs(Kn-1) = 2.
Teorema 4.4.1:
Jika P adalah graf Petersen dengan himpunan titik V dan 
= n dan δ(G) = 3
maka berlaku
≤ t υ ѕ (P) ≤
Teorema 4.3.1 berlaku untuk graf r-reguler dengan r = n –1, dan Teorema 4.4.1 berlaku untuk graf Petersen.