NILAI TOTAL KETIDAKTERATURAN TITIK DARI SUBDIVISI GRAF BINTANG 푆 UNTUK 푚 ≥ 9, 푛 ≥ 3

ON THE TOTAL VERTEX IRREGULARITY STRENGTH OF SUBDIVISION OF STAR 푆 FOR 푚 ≥ 9,푛 ≥ 3

Nurfuaidah Suardi1, Nurdin2, Hasmawati2

1Matematika Terapan, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Hasanuddin, 2Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam,

Universitas Hasanuddin

Alamat Korespondensi: Nurfuaidah Suardi Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Hasanuddin Makassar, 90245 HP : 085696506261 Email: nurfuaidah.suardi@gmail.com

Abstrak Penelitian ini merupakan pengembangan dari penelitian Siddiqui dkk. yang telah menentukan nilai total ketidakteraturan titik dari subdivisi graf bintang푆 untuk 1 ≤ 푚 ≤ 8 dan 푛 ≥ 3, namun pencarian subdivisi graf bintang 푆 untuk 푚 ≥ 9 dan 푛 ≥ 3 masih merupakan masalah terbuka. Penelitian ini bertujuan untuk menentukan nilai total ketidakteraturan titik dari subdivisi graf bintang푆 untuk 푚 ≥ 9 dan 푛 ≥ 3. Metode penelitian yang digunakan adalah kajian teoritis dengan menentukan batas bawah terbesar dan batas atas terkecil. Batas bawah dianalisis berdasarkan sifat-sifat graf, sedangkan batas atas dianalisis dengan mengkonstruksi fungsi pelabelan total tidak teratur. Hasil penelitian memberikan konstruksi pelabelan total, sedemikan sehingga semua titik pada subdivisi graf bintang mempunyai bobot berbeda. Disimpulkan bahwa nilai total ketidakteraturan titik dari subdivisi graf bintang 푆 adalah bilangan bulat terkecil yang lebih besar atau sama dengan sepertiga dari banyaknya titik pada subdivisi graf bintang.

Kata Kunci : Pelabelan total tidak teratur titik, nilai total ketidakteraturan titik, subdivisi graf bintang Abstract This research is development from Siddiqui et al.’s research which had determined total vertex irregularity strength of subdivision of star 푆 for 1 ≤ 푚 ≤ 8 and 푛 ≥ 3, but the search of subdivision of star for 푚 ≥ 9 and 푛 ≥ 3 is still an open problem. This research aimed to determine the total vertex irregularity strength of subdivision of star 푆 for 푚 ≥ 9 and 푛 ≥ 3. Methods of research is using a theoretical study by determine lower bound and upper bound. The lower bound was analyzed by characteristic of graph, while the upper bound was analyzed by construct the function irregular total labeling. The result of research gives construction total labeling, such that each vertex of subdivision of star has a distinct weight. The conclusion is the total vertex irregularity strength of subdivision of star 푆 is the smallest integer not less than a third of cardinality of the vertex of subdivision of star. Keyword : vertex irregular total labeling, total vertex irregularity strength, subdivision of star

PENDAHULUAN

Pelabelan graf merupakan salah satu topik dalam teori graf yang semakin berkembang,

baik secara teoritis maupun dalam aplikasi. Pelabelan graf didefinisikan sebagai suatu

pemetaan yang memetakan himpunan bagian unsur-unsur dari graf ke suatu himpunan

bilangan (umumnya himpunan bilangan bulat positif atau non-negatif), yang diperkenalkan

oleh Sedláček (1963). Pelabelan dengan domain himpunan titik disebut pelabelan titik,

pelabelan dengan domain himpunan sisi disebut pelabelan sisi, serta pelabelan dengan domain

gabungan himpunan titik dan himpunan sisi disebut pelabelan total (Wallis, 2007).

Salah satu jenis pelabelan pada graf adalah pelabelan tidak teratur. Pelabelan tidak

teratur (irregular labeling) pada graf 퐺 didefinisikan sebagai suatu pemetaan yang

memetakan himpunan sisi dari 퐺 ke himpunan bilangan bulat positif, sedemikian sehingga

semua titik mempunyai bobot yang berbeda (Chartrand dkk., 1988).

Dalam pengembangan pelabelan tidak teratur, Baca dkk., (2007) memperkenalkan

pelabelan tidak teratur yang didasarkan pada pelabelan total, yaitu pelabelan total tidak teratur

titik (vertex irregular total labeling). Pelabelan total tidak teratur titik pada graf 퐺

didefinisikan sebagai suatu pemetaan yang memetakan himpunan titik dan sisi dari 퐺 ke

himpunan bilangan {1,2, . . . , 푘}, sedemikian sehingga semua titik mempunyai bobot yang

berbeda. Bobot titik 푣 adalah jumlah label titik 푣 dan label sisi yang terkait pada 푣. Nilai total

ketidakteraturan titik dari 퐺, dinotasikan dengan 푡푣푠(퐺), adalah bilangan bulat positif terkecil

푘 sedemikian sehingga 퐺 mempunyai pelabelan−푘 total tidak teratur titik.

Survei hasil-hasil penelitian tentang nilai total ketidakteraturan dari suatu graf yang

telah diperoleh peneliti lainnya (Gallian, 2013). Bača dkk., (2007) telah memberikan suatu

batas atas nilai total ketidakteraturan titik dari graf pohon dan juga telah menentukan nilai

total ketidakteraturan titik dari graf bintang, yaitu bilangan bulat terkecil yang lebih besar atau

sama dengan setengah dari banyaknya titik pada graf bintang. Anholcer dkk., (2009)

memberikan batas atas yang baru untuk nilai total ketidakteraturan titik pada graf. Nurdin

dkk., (2010) telah memberikan batas bawah nilai total ketidakteraturan titik pada graf

(Teorema 2). Ahmad dkk., (2011) menentukan nilai total ketidakteraturan titik dari graf helm,

graf friendship diperumum, graf flower dan graf web. Untuk beberapa graf pohon tertentu,

Nurdin (2012) menentukan nilai total ketidakteraturan titik dari graf quadtree dan banana

tree.

Subdivisi graf bintang (subdivision of star), dinotasikan 푆 adalah graf yang diperoleh

dari graf bintang dengan menambah 푚 titik pada setiap sisinya. (Siddiqui dkk., 2011).

Siddiqui dkk., (2011) telah menentukan nilai total ketidakteraturan titik dari subdivisi graf

bintang 푆 untuk 1 ≤ 푚 ≤ 8 dan 푛 ≥ 3, namun pencarian subdivisi graf bintang 푆 untuk

푚 ≥ 9 dan 푛 ≥ 3 masih merupakan masalah terbuka. Dengan demikian, penelitian ini

bertujuan untuk menentukan nilai total ketidakteraturan titik dari subdivisi graf bintang 푆

untuk 푚 ≥ 9 dan 푛 ≥ 3.

BAHAN DAN METODE

Rancangan Penelitian

Penelitian ini merupakan kajian teoritis dengan menggunakan definisi himpunan titik

dan himpunan sisi, mengkonstruksi suatu pelabelan yakni melabeli semua sisi dan titik graf 퐺

dengan angka 1,2, … , 푘, dalam pelabelan tersebut dimungkinkan adanya sisi atau titik yang

mempunyai label sama, menghitung bobot sehingga fungsi bobot berbeda, menunjukkan

푘adalah label terbesar yang digunakan.

Analisis Data

Metode yang digunakan dalam menentukan nilai total ketidakteraturan titik dari

subdivisi graf bintang, yaitu dengan menentukan batas bawah terbesar dan batas atas terkecil.

Batas bawah dianalisis berdasarkan sifat-sifat graf dan teorema pendukung, sedangkan batas

atas dianalisis dengan mengkonstruksi fungsi pelabelan total tidak teratur.

HASIL PENELITIAN

Teorema 1. Untuk 푚 ≥ 9 dan 푛 ≥ 3, maka 푡푣푠(푆 ) = .

dengan konstruksi suatu pelabelan total pada 푆 sebagai berikut:

Misal푘 , =(푚 + 1 − 푗)푛 + 푖 + 1

3 ,

Definisikan label titik dari 푆 sebagai berikut. Untuk 1 ≤ 푖 ≤ 푛,

푓(푐) =푚푛 + 푛 + 1

3 ;

푓 푥 , =

⎩⎪⎪⎪⎨

⎪⎪⎪⎧

푚푛 + 푖 + 1 − 2푘 , untuk 푗 = 1;

(푚 − 1)푛 + 푖 + 1 − 푘 , − 푘 , untuk 푗 = 2;

(푚 + 1 − 푗)푛 + 푖 + 1 − 푘 , − 푘 , untuk 3 ≤ 푗 ≤ 푚;

푖 + 1 − 푘 , untuk 푗 = 푚 + 1;

dan definisikan label sisi dari 푆 sebagai berikut. Untuk 1 ≤ 푖 ≤ 푛,

푓 푐푥 , =푚푛 + 푛 + 1

3 ;

푓 푥 , 푥 , =

⎩⎪⎨

⎪⎧

푚푛 + 푛 + 1

3 untuk푗 = 2;

(푚 + 1 − 푗)푛 + 푖 + 13 untuk3 ≤ 푗 ≤ 푚 + 1

.

Ilustrasi nilai total ketidakteraturan titik pada graf 푆 dengan 푡푒푠(푆 ) = 26 dapat

dilihat pada Gambar 1 (lampiran).

PEMBAHASAN

Penelitian ini menemukan nilai total ketidakteraturan titik dari subdivisi graf bintang 푆

untuk 푚 ≥ 9 dan 푛 ≥ 3sebagai berikut:

Subdivisi graf bintang 푆 memiliki 푚푛 + 푛 + 1 titik dan 푚푛 + 푛 sisi. Graf 푆

memiliki 1 titik berderajat 푛, 푛 titik berderajat 1 dan 푚푛 titik berderajat 2. Didefinisikan

himpunan titik dan himpunan sisi dari subdivisi graf bintang 푆 yaitu:

푉(푆 ) = {푐} ∪ 푥 , |1 ≤ 푖 ≤ 푛dan1 ≤ 푗 ≤ 푚 + 1 ,

퐸(푆 ) = 푐푥 , |1 ≤ 푖 ≤ 푛 ∪ 푥 , 푥 , |1 ≤ 푖 ≤ 푛dan2 ≤ 푗 ≤ 푚 + 1 .

Dalam penelitian ini, batas bawah nilai total ketidakteraturan titik akan ditentukan

dengan menggunakan teorema sebagai berikut:

Teorema 2. Misalkan 퐺 adalah suatu graf yang mempunyai 푛 titik berderajat 푖 dengan

푖 = 훿, 훿 + 1, 훿 + 2, … ,∆ dengan 훿 dan ∆= ∆(퐺) masing-masing adalah derajat minimum dan

derajat maksimum titik dari 퐺, maka

푡푣푠(퐺) ≥ maks훿 + 푛훿 + 1 ,

훿 + 푛 + 푛훿 + 2 , … ,

훿 + ∑ 푛∆

∆ + 1 .

Untuk membuktikan hasil penelitian (Teorema 1), digunakan teorema 2 sehingga

diperoleh bahwa, 푡푣푠(푆 ) ≥ . Selanjutnya untuk membuktikan bahwa 푡푣푠(푆 ) ≤

, dikonstruksi suatu pelabelan total pada 푆 . Berdasarkan definisi pelabelan total 푓

pada 푆 tersebut, diperoleh bobot titik-titik dari 푆 adalah sebagai berikut:

Fakta 1. Untuk 1 ≤ 푖 ≤ 푛,

푤푡(푐) = 푓(푐) + 푓 푐푥 , = (1 + 푛)푚푛 + 푛 + 1

3 .

Fakta 2. Untuk 1 ≤ 푖 ≤ 푛 dan 푗 = 1,

푤푡 푥 , = 푓 푥 , + 푓 푐푥 , + 푓 푥 , 푥 , = 푚푛 + 푖 + 1.

Fakta 3. Untuk 1 ≤ 푖 ≤ 푛 dan 푗 = 2,

푤푡 푥 , = 푓 푥 , + 푓 푥 , 푥 , + 푓 푥 , 푥 , = (푚− 1)푛 + 푖 + 1.

Fakta 4. Untuk 1 ≤ 푖 ≤ 푛 dan 3 ≤ 푗 ≤ 푚,

푤푡(푥 , ) = 푤푡 푥 , = 푓 푥 , + 푓 푥 , 푥 , + 푓 푥 , 푥 , = (푚 + 1 − 푗)푛 + 푖 + 1.

Fakta 5. Untuk 1 ≤ 푖 ≤ 푛 dan 푗 = 푚 + 1,

푤푡 푥 , = 푓 푥 , + 푓 푥 , 푥 , = 푖 + 1.

Berdasarkan lima fakta tersebut, diperoleh bahwa bobot setiap titik dari 푆 berbeda.

Dengan kata lain, 푓 merupakan suatu pelabelan total tidak teratur titik pada 푆 .

Selanjutnya akan ditunjukkan bahwa label terbesar yang digunakan dengan pelabelan

total 푓 adalah . Berdasarkan definisi pelabelan total 푓, diperoleh sebagai berikut:

Fakta 1. 푓(푐) = .

Fakta 2. 푓 푥 , ≤ 푓 푥 , ≤ .

Fakta 3. 푓 푥 , ≤ 푓 푥 , ≤ .

Fakta 4. 푓 푥 , ≤ 푓 푥 , ≤ 푓 푥 , ≤ 푓 푥 , ≤ .

Fakta 5. 푓 푥 , ≤ 푓 푥 , ≤ .

Fakta 6. 푓 푥 , ≤ 푓 푥 , ≤ untuk 1 ≤ 푗 ≤ 푚.

Fakta 7. 푓 푐푥 , = .

Fakta 8. 푓 푥 , 푥 , = .

Fakta 9. 푓 푥 , 푥 , ≤ 푓 푥 , 푥 , ≤ 푓 푥 , 푥 , ≤ 푓 푥 , 푥 , ≤ .

Fakta 10. 푓 푥 , 푥 , ≤ 푓 푥 , 푥 , ≤ untuk 3 ≤ 푗 ≤ 푚.

Dengan demikian, pelabelan total 푓 merupakan pemetaan dari 푉 ∪ 퐸 ke

1,2,3, … , . Karena 푓 merupakan suatu pelabelan total tidak teratur titik pada 푆

dan label terbesar yang digunakan adalah . Maka, 푡푣푠(푆 ) ≤ .

Karena 푡푣푠(푆 ) ≥ dan 푡푣푠(푆 ) ≤ , maka 푡푣푠(푆 ) = . ∎

KESIMPULAN DAN SARAN

Disimpulkan bahwa nilai total ketidakteraturan titik dari subdivisi graf bintang 푆

untuk 푚 ≥ 9 dan 푛 ≥ 3 adalah ⌈(푚푛 + 푛 + 1)/3⌉, dengan fungsi pelabelan total yang

dikonstruksi, sedemikan sehingga semua titik pada subdivisi graf bintang 푆 mempunyai

bobot berbeda. Disarankan pada peneliti selanjutnya untuk menentukan nilai total

ketidakteraturan sisi dan titik 푡푠(퐺) dari subdivisi graf bintang 푆 .

UCAPAN TERIMA KASIH

Penulis mengucapkan terima kasih kepada Dr. Nurdin, M.Si dan Dr. Hasmawati, M.Si

serta semua pihak yang telah membantu dalam penulisan artikel ini.

DAFTAR PUSTAKA

Ahmad A., Awan K.M., Javaid I. & Slamin. (2011). Total Vertex Irregularity Strength of Wheel Related Graphs. Australasian Journal of Combinatorics, 51:147-156.

Anholcer M., Kalkowski M. & Przybylo J. (2009). A New Upper Bound for the Total Vertex Irregularity Strength of Graphs. Discrete Mathematics, 309:6316-5317.

Bača M., Jendrol' S., Miller M. & Ryan J. (2007). On Irregular Total Labellings. Discrete Mathematics, 307:1378-1388.

Chartrand G., Jacobson M., Lehel J., Oellermann O., Ruiz S. & Saba F. (1988). Irregular Network. Congressus Numerantium, 64:187-192.

Gallian J.A. (2013). A Dynamic Survey of Graph Labeling. Electron Journal of Combinatorics, 16: 191-194.

Nurdin. (2012). On the Total Vertex Irregularity Strengths of Quadtrees and Banana Trees. Journal of the Indonesian Mathematical Society, 18(1):31-36.

Nurdin, Baskoro E.T., Salman A.N.M. & Gaos N.N. (2010). On the Total Vertex Irregularity Strength of Trees. Discrete Mathematics, 310:3043-3048.

Sedláček J. (1963). Problem 27, In: Theory of Graphs and Its Applications, Proceedings of the Symposium Smolenice, 163–167.

Siddiqui M.K. & Afzal D. (2011). On tvs of Subdivision of Star Sn. Australian Journal of Basic and Applied Sciences, 5(11):2146-2156.

Wallis W.D. (2007). A Beginner’s Guide to Graph Theory, 2nd edition. Berlin: Birkhäuser Boston.

LAMPIRAN

Gambar 1. Pelabelan-ퟐퟔ total tidak teratur titik pada 푺ퟕퟏퟎ

푐26

26

26

26

26

26

26

20 19 26 7 5 3 21 20 19 17 16 15 14 13 12 10 9 8 6

21 20 26 7 5 4 21 20 19 18 17 15 14 13 12 11 10 8 6

22 21 26 8 5 4 22 20 19 18 17 16 15 13 12 11 10 9 6

23 21 26 8 6 4 22 21 20 18 17 16 15 14 13 11 10 9 7

24 22 26 8 6 5 22 21 20 19 18 16 15 14 13 12 11 9 7

25 23 26 9 6 5 23 21 20 19 18 17 16 14 13 12 11 10 7

푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 ,

푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 ,

푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 ,

푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 ,

푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 ,

푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 ,

26 23 26 9 7 5 23 22 21 19 18 17 16 15 14 12 11 10 8 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 , 푥 ,

26

1 1

2 1

2 2

3 2

4 2

4 3

5 3