KEKUATAN TAK REGULER SISI TOTAL, TITIK TOTAL DAN TOTAL PADA BEBERAPA KELAS GRAF.

Misal G(V, E) selanjutnya disingkat G adalah graf sederhana (tidak memu- at loop dan sisi paralel). Pelabelan suatu graf didefinisikan sebagai pemetaan yang membawa elemen-elemen graf ke bilangan-bilangan bulat positif atau non-negatif. Jika domain pemetaan adalah himpunan titik (V ), maka pelabelan disebut pelabel- an titik (vertex labeling), yaitu fungsi ƒ : V → Z≥0. Jika domainnya adalah him- punan sisi (E), maka pelabelan disebut pelabelan sisi (edge labeling), yaitu fungsi ƒ : E → Z≥0 . Jika domainnya adalah himpunan titik maupun sisi (V ∪ E) maka pe- labelan disebut pelabelan total (total labeling), yaitu fungsi f : V ∪E → Z≥0. Suatu pelabelan-k total adalah pelabelan total ƒ : V ∪ E → {1, 2, 3, . . . , k} dengan k ada- lah bilangan bulat. Pelabelan graf dapat dilakukan dengan cara mengaitkan jumlah label dengan elemen-elemen graf. Jumlah label ini dikenal sebagai bobot (weight) dari elemen graf. Misal diketahui pelabelan total ƒ : V ∪ E → {1, 2, 3, . . .}. Bobot titik x pada pelabelan total f didefinisikan sebagai wt(x) = ƒ (x) + Σxy∈E ƒ (xy) se- dangkan bobot sisi xy adalah wt(xy) = ƒ (x)+ ƒ (xy)+ ƒ (y). Pemetaan ƒ : V ∪E →{1, 2, 3, . . . , k} disebut pelabelan-k total tak reguler sisi/titik (edge/ vertex irregu- lar total k-labeling) pada G, jika bobot setiap pasang sisi/titik yang berbeda pada G tidak sama, yaitu ƒ (x) + ƒ (xy) + ƒ (y) = ƒ (u) + ƒ (uv) + ƒ (v) untuk setiap dua sisi xy dan uv yang berbeda pada G atau pada total tak reguler titik berlaku ƒ (x) + Σxy∈E ƒ (xy) = ƒ (u) + Σuv∈E ƒ (uv) untuk setiap dua titik x dan u yang berbeda pada G. Kekuatan tak reguler sisi/titik total (total edge/ vertex irregularity strength) dari graf G, dinotasikan dengan tes(G)/ tvs(G) , didefinisikan sebagai bi- langan bulat positif terkecil k sehingga G mempunyai pelabelan-k total tak reguler sisi/titik. Penelitian disertasi ini dimotivasi oleh adanya hasil untuk kekuatan tak re- guler total pada graf-graf pohon (yaitu graf-graf acyclic) dengan memperhatikan banyaknya sisi atau titik daun. Dari itu muncul pemikiran bagaimana jika keku- atan tak reguler total ditentukan pada graf-graf cyclic dan dengan memperhatikan banyaknya sisi atau titik daun pula. Pada perkembangannya, jika tiap pasang sisi atau titik mempunyai bobot sisi dan bobot titik yang berbeda secara simultan, ma- ka pelabelannya di sebut pelabelan-k total tak reguler total (totally irregular total k-labeling) pada G. Jenis pelabelan ini belum banyak dikaji orang dan hasil-hasil untuk graf-graf pohon maupun graf cyclic belum diperoleh nilai eksaknya. Oleh ka- rena itu, untuk jenis pelabelan total ini, penulis mengawali mengkaji untuk graf-graf pohon terlebih dahulu dan sebagai langkah awal diselidiki pada graf caterpillar. Penentuan nilai eksak kekuatan tak reguler sisi, titik atau total dilakukan dengan cara menunjukkan nilai batas bawah maupun batas atas yang keduanya dibuktikan bernilai sama. Beberapa peneliti telah memperoleh batas bawah keku- atan tak reguler sisi, titik atau total untuk graf-graf pohon dengan memperhatikan banyak sisi daun ataupun graf-graf sebarang dengan memperhatikan derajat titik pada graf. Batas atas ditentukan dengan cara mengkonstruksi suatu pelabelan total sehingga diperoleh label terbesar seminimum mungkin. Dengan kedua langkah tersebut, diperoleh nilai untuk kekuatan tak reguler sisi, titik atau total pada graf. Sebagai validasi, bukti-bukti diberikan dalam bentuk teorema ataupun lemma. Pada penelitian ini telah diperoleh hasil-hasil untuk kekuatan tak reguler sisi atau titik pada graf-graf cyclic dan memperhatikan titik daun, yaitu pada graf-graf helm diperumum, gir diperumum, web diperumum, prisma diperumum dan korona graf dengan titik-titik terisolasi. Sedangkan hasil-hasil untuk kekuatan tak reguler total diperoleh pada graf-graf pohon (acyclic), dalam hal ini adalah graf bintang, dobel-bintang dan dobel bintang dengan cut vertex pada sisi penghubung dua pusat bintang, yang selanjutnya disebut graf caterpillar