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 1
Matematika 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:
[email protected]
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 memetakan himpunan sisi dari
didefinisikan sebagai suatu pemetaan yang
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
ketidakteraturan titik dari , dinotasikan dengan sedemikian sehingga
dan label sisi yang terkait pada . Nilai total ( ), adalah bilangan bulat positif terkecil
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 dari graf bintang dengan menambah
adalah graf yang diperoleh
titik pada setiap sisinya. (Siddiqui dkk., 2011).
Siddiqui dkk., (2011) telah menentukan nilai total ketidakteraturan titik dari subdivisi graf untuk 1 ≤
bintang ≥ 9 dan
≤ 8 dan
≥ 3, namun pencarian subdivisi graf bintang
untuk
≥ 3 masih merupakan masalah terbuka. Dengan demikian, penelitian ini
bertujuan untuk menentukan nilai total ketidakteraturan titik dari subdivisi graf bintang ≥ 9 dan
untuk
≥ 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 Misal
,
=
(
sebagai berikut:
sebagai berikut. Untuk 1 ≤ ≤ ,
+ +1 ; 3
( )= ⎧ ⎪ ⎪( ⎪ =
.
+1− ) + +1 , 3
Definisikan label titik dari
,
)=
+ +1−2
,
− 1) + + 1 −
,
⎨( + 1 − ) + + 1 − ⎪ ⎪ ⎪ +1− , ⎩
−
,
,
−
,
untuk
= 1;
untuk
= 2;
untuk 3 ≤ ≤ untuk
=
;
+ 1;
sebagai berikut. Untuk 1 ≤ ≤ ,
dan definisikan label sisi dari + +1 ; 3
=
,
+ +1 untuk = 2; 3 +1− ) + +1 untuk 3 ≤ ≤ + 1. 3
⎧ ⎪ ,
=
,
⎨( ⎪ ⎩
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
≥ 3 sebagai berikut:
Subdivisi graf bintang memiliki 1 titik berderajat
+
memiliki ,
+ 1 titik dan
titik berderajat 1 dan
(
)=
)={ }∪ ,
|1 ≤ ≤
,
yaitu:
|1 ≤ ≤ dan 1 ≤ ≤
∪
,
,
sisi. Graf
titik berderajat 2. Didefinisikan
himpunan titik dan himpunan sisi dari subdivisi graf bintang (
+
+1 ,
|1 ≤ ≤ dan 2 ≤ ≤
+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
= , + 1, + 2, … , ∆ dengan
titik berderajat
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 pada
tersebut, diperoleh bobot titik-titik dari
,
)≤
. Berdasarkan definisi pelabelan total adalah sebagai berikut:
Fakta 1. Untuk 1 ≤ ≤ , ( )= ( )+
(
= (1 + )
+ +1 . 3
Fakta 2. Untuk 1 ≤ ≤
dan = 1, =
,
Fakta 3. Untuk 1 ≤ ≤
,
)=
+
,
Fakta 4. Untuk 1 ≤ ≤ (
,
+
,
=
,
+ + 1.
Fakta 5. Untuk 1 ≤ ≤
,
dan =
,
=(
,
,
− 1) + + 1.
+
,
=(
+ 1 − ) + + 1.
+ 1, =
,
,
,
+
,
+
,
dan 3 ≤ ≤ =
,
,
dan = 2,
=
,
+
,
+
,
,
= + 1.
,
Berdasarkan lima fakta tersebut, diperoleh bahwa bobot setiap titik dari Dengan kata lain,
merupakan suatu pelabelan total tidak teratur titik pada
berbeda.
.
Selanjutnya akan ditunjukkan bahwa label terbesar yang digunakan dengan pelabelan total
. Berdasarkan definisi pelabelan total , diperoleh sebagai berikut:
adalah
Fakta 1. ( ) =
.
Fakta 2.
,
≤
,
≤
.
Fakta 3.
,
≤
,
≤
.
Fakta 4.
,
Fakta 5.
,
Fakta 6.
,
Fakta 7. ,
Fakta 9.
,
≤
,
≤
,
untuk 1 ≤ ≤
. ≤
,
≤
,
≤
, ,
≤
pelabelan total
. Karena
(
)≥
,
,
≤
,
≤
,
untuk 3 ≤ ≤
.
.
merupakan pemetaan dari
∪
ke
merupakan suatu pelabelan total tidak teratur titik pada . Maka,
dan label terbesar yang digunakan adalah Karena
.
.
Dengan demikian, 1,2,3, … ,
.
.
≤
= ,
≤
,
≤
= ,
,
,
≤
,
,
≤ ,
Fakta 8.
Fakta 10.
≤
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 12 20 26 19 20 21 17 19 9 15 16 13 14 10 8 26
,
,
,
,
,
,
,
6 ,
21 26 20 20 21 18 19 12 10 15 17 13 14 11 8 6
26
,
,
,
,
,
,
,
26
,
,
,
,
,
,
,
,
,
,
,
,
,
7
,
5
8
4
5
,
1 ,
1
2 ,
,
4
5
,
8
1
,
,
,
26 23 26 21 21 22 18 20 13 10 16 17 14 15 11 9 7
3
,
,
22 26 21 20 22 18 19 12 10 16 17 13 15 11 9 6 26
7
2
,
4
6
,
2 ,
2
3 ,
,
26 24
26
22
,
26 25 26
,
22
,
26
23
,
26
21
23 ,
20
,
21
23
,
26
19
23 ,
18 14 15 12 13 9 11 7
,
19
20
,
22
16
,
17
21
,
17
,
Gambar 1. Pelabelan-
,
,
18 14 16 12 13 10 11 7
,
19
,
,
,
,
,
,
total tidak teratur titik pada
5
6
,
9
,
18 15 16 12 14 10 11 8 ,
8
5
6
,
3
7 ,
4 ,
,
5
4 ,
,
,
9
2
3
5 ,
