Jurnal Ilmiah Matematika dan Pendidikan Matematika (JMP) Vol. 10 No. 2, Desember 2018, hal. 9-16 ISSN (Cetak) : 2085-1456; ISSN ( Online ) : 2550-0422

## PELABELAN TOTAL TAK REGULER PADA BEBERAPA GRAF
Nugroho Arif Sudibyo
STMIK Duta Bangsa nugroho_arifs@stmikdb.ac.id

## Siti Komsatun
STMIK Duta Bangsa
ABSTRACT. For a simple graph G with vertex set V (G) and edge set E(G), a labeling ( )    ( )   *          + is  called  a  vertex  irregular  total  k- labeling of G if for any two diferent vertices x and y, their weights wt(x) and wt(y) are distinct.  The weight wt(x) of a vertex x in G is the sum of its label and the labels of all edges incident with the given vertex x.  The total vertex irregularity strength of G, tvs(G), is the smallest positive integer k for which G has a vertex irregular total k-labeling.  In this paper, we study the total vertex irregularity strength of some class of graph.
Keywords : total vertex irregularity strength .
ABSTRAK. Misal adalah graf sederhana dengan himpunan titik ( ) dan himpunan garis ( ) , pelabelan ( )    ( )   *          + disebut pelabelan k -total tak reguler titik  pada G , jika  setiap  dua  titik dan ,  bobot  dari ( ) dan ( ) berbeda.  Bobot ( ) dari  suatu  titik di adalah  jumlah  dari  label  titik dan  label  dari  garis  yang terhubung dengan titik . Pelabelan k -total tak reguler titik, ( ) , adalah bilangan bulat positif terkecil k dari G yang mempunyai pelabelan k -total tak reguler. Pada makalah ini, akan dibahas pelabelan total tak reguler titik dari beberapa kelas graf.
Kata Kunci : pelabelan total tak reguler titik .

## 1. PENDAHULUAN
Pada  tahun  1735,  teori  graf  pertama  kali  diperkenalkan  Leonhard  Euler untuk  menyelesaikan  permasalahan  jembatan  Konigsberg  pada  sungai  Pregel, Rusia.  Selanjutnya  teori  graf  berkembang  luas  dan  dapat  diterapkan  pada kehidupan nyata. Pelabelan graf merupakan suatu topik yang menarik dalam teori graf sehingga berbagai jenis pelabelan diteliti dan dikembangkan (Gallian, 2017).
Hingga  saat  ini  pelabelan  graf  dapat  diaplikasikan  pada  berbagai  bidang antara  lain  sistem  transportasi,  sistem  komunikasi,  navigasi  geografis,  radar,  dan juga  sistem  keamanan.  Sebagai  contoh  desain  dari  kode  untuk  sinyal  radar  dan peluru kendali ekuivalen dengan pelabelan pada graf lengkap, dimana setiap titik yang  ada  dihubungkan  dengan  satu  sisi  yang  mempunyai  label  yang  selalu

## 10 Nugroho Arif Sudibyo dan Siti Komsatun
berbeda. Label sisi ini menggambarkan jarak antar titik, sedangkan label titiknya merupakan posisi pada saat sinyal dikirimkan.
Pelabelan graf adalah suatu pemberian nilai (dengan bilangan bulat) pada titik atau sisi dari graf atau keduanya sehingga memenuhi kondisi tertentu. Label yang  digunakan  berupa  bilangan  bulat  positif  atau  bilangan  asli.  Pelabelan  graf pertama kali diperkenalkan pada akhir 1960an oleh Rosa. Selanjutnya, pelabelan yang  domainnya  berupa  himpunan  titik,  himpunan  sisi,  atau  keduanya  biasanya disebut  dengan  pelabelan  titik,  pelabelan  sisi,  dan  pelabelan  total.  Hingga  kini dikenal beberapa jenis pelabelan graf yang dibahas, antara lain pelabelan graceful, pelabelan harmoni, pelabelan total tak beraturan, pelabelan ajaib, pelabelan radio, pelabelan anti ajaib, dan masih banyak pelabelan graf yang lain (Gallian, 2017).
Misal adalah graf sederhana dengan himpunan titik ( ) dan himpunan garis ( ) , pelabelan ( )    ( )   *          + disebut pelabelan k -total tak reguler  titik  pada G ,  jika  setiap  dua  titik dan ,  bobot  dari ( ) dan ( ) berbeda. Bobot ( ) dari suatu titik di adalah jumlah dari label titik dan label dari garis yang terhubung dengan titik . Pelabelan k -total tak reguler titik,
( ) , adalah bilangan bulat positif terkecil k dari G yang mempunyai pelabelan k -total tak reguler.
Penentuan  kekuatan  tak  regular  titik  total  suatu  graf  juga  bukan  hal  yang mudah  dilakukan.  Bača  dkk.  (2007)  telah  menghasilkan  batas  bawah  dan  batas atas  kekuatan  tak  reguler  titik  total  untuk  graf  dengan p titik  dan q sisi (dinotasikan  dengan  ( p,q )-graph),  yang  mempunyai  derajat  minimum  =  ( ) dan derajat maksimum  =  ( G ) yaitu
⌈   ⌉ tvs ( G ) p +  - 2  + 1. (1)
Pada  artikel  yang  sama,  Bača  dkk.  (2007)  juga  telah  menghasilkan kekuatan tak reguler titik total untuk graf bintang, graf lengkap, graf lingkaran dan graf  prisma.  Nurdin  dkk.  (2010)    menghasilkan  kekuatan  tak  reguler  titik  total untuk  beberapa  graf  pohon.  Wijaya  dan  Slamin  (2008)  serta  Wijaya  dkk.  (2005) telah memperoleh kekuatan tak reguler titik total untuk graf roda, graf kipas, graf matahari, graf friendship dan graf bipartit lengkap. Pada makalah ini akan dibahas
Pelabelan Total tak Reguler pada beberapa Graf                                                               11
kekuatan  tak  reguler  titik  total  untuk  graf ladder  rung ,  modifikasi  graf caveman dan graf double star dan bagaimana formula pelabelan untuk mendapatkannya.

## 2. METODE PENELITIAN
Penelitian  ini  merupakan  kajian  ilmu  murni  yang  bersifat  studi  literatur. Oleh karena itu, pendekatan yang digunakan adalah eksploratif dan adaptasi yaitu memanfaatkan  pengetahuan  yang  penulis  miliki  dari  penelitian-penelitian sebelumnya.  Selain  itu  digunakan  juga  hasil-hasil  penelitian  yang  telah  ada  di literatur.
1. Menelusuri  pustaka  yang  berupa  buku-buku  referensi,  jurnal,  artikel  dan mengkaji  konsep-konsep  dasar  yang  berkaitan  dengan  graf,  pelabelan  pada graf  dan  khususnya  pelabelan  total  tak  regular,  kemudian  mempelajari  dan mengkaji beberapa hasil penelitian tentang pelabelan total tak reguler titik.
2. Melakukan  penelitian  tentang  pelabelan  total  tak  reguler  titik  pada  ketiga kelas graf dan menentukan kekuatan tak reguler titik total ( tvs ( G )) pada graf- graf tersebut yang hasilnya disajikan dalam bentuk teorema.
3. Membuktikan  teorema  yang  diperoleh  di  langkah  3.  Untuk  hal  ini,  detil langkahnya adalah sebagai berikut:
a. melakukan simulasi pelabelan total tak reguler titik pada graf tersebut di langkah ke 3 dengan jumlah titik ( n ) tertentu.
b. menentukan  rumus  pelabelan  total  tak  regular  titik  untuk n sebarang pada graf tersebut ,

## 3. HASIL DAN PEMBAHASAN
Graf ladder  rung berorder n adalah  graf  gabungan  dari n copies dari graf path (Ball  and  Coxeter,  1987).  Graf ladder  rung disajikan  pada Gambar 1.
Gambar 1. Graf ladder rung .
Teorema 1. Diberikan graf ladder rung , n  2 maka kekuatan total tak reguler titik totalnya adalah
( )
Bukti. Graf ladder rung merupakan graf yang memiliki 2 n titik ( ) dan setiap titik  berdegree  1.  Dengan  menggunakan  Teorema  pada  Bača  dkk.  (2007) diperoleh ( ) Selanjutnya akan ditunjukkan bahwa ( ) .  Misalkan  himpunan  titik ( ) * + dan  himpunan egde (garis) ( ) *
+ . Pelabelan  titik  dan  pelabelan  garis adalah sebagai berikut.
( ) untuk setiap
( ) untuk setiap
dan
( ) untuk setiap
Oleh  karena  bobot  setiap  titik  berbeda,  maka  terbukti  kekuatan  total  tak  reguler titik totalnya adalah ( ) . □ The  graf caveman adalah  graf  yang  terbentuk  dalam  teori  jaringan  sosial yang  dibentuk  dengan  memodifikasi  satu  set k-cliques terisolasi  ( cave )  dengan menghilangkan satu sisi dari setiap cliques dan menggunakannya untuk terhubung ke neighboring cliques sepanjang cliques pusat sedemikian rupa sehingga semua n cliques membentuk loop tunggal  tak  terputus  (Watts,  1999).  Pada  makalah  ini
1 u 2 u n u 1 v 2 v n v
Pelabelan Total tak Reguler pada beberapa Graf                                                               13
akan dibahas modifikasi dari graf caveman yaitu sebanyak n copy graf lengkap yang dihubungkan dengan suatu cliques , seperti yang disajikan pada Gambar 2.
Gambar 2. modifikasi graf caveman n C .
Teorema  2. Diberikan  modifikasi  graf caveman n C maka  kekuatan  total  tak reguler titik totalnya adalah
. 1 ) (   n C tvs n
Bukti. Modifikasi graf caveman n C merupakan graf yang memiliki 5 n titik ( ) , degree minimumnya adalah 4 ( ) dan degree maksimumnya adalah 5 ( ) . Dengan menggunakan  Teorema  pada  Bača  dkk.(2007)  diperoleh ( ) Selanjutnya  akan  ditunjukkan  bahwa ( ) .  Misalkan  himpunan  titik ( ) { } , p elabelan titik dan pelabelan garis adalah sebagai berikut.
( ) untuk setiap dan
dan
( ) untuk setiap dan ( ) untuk setiap dan .
Selanjutnya,  pelabelan  garis  untuk  modifikasi  graf caveman n C adalah  sebagai berikut.
( ) untuk setiap dan .
Oleh  karena  bobot  setiap  titik  berbeda,  maka  terbukti  kekuatan  total  tak  reguler titik totalnya adalah . 1 ) (   n C tvs n
□
Graf double star n m S , adalah suatu graf dua graf star yang mempunyai dua titik  sentral x dan y yang adjacent .  Pada  graf double  star terdapat m daun
m x x x , , , 2 1  yang adjacent pada x dan n daun n y y y , , , 2 1  yang adjacent pada y (Gallian, 2017). Graf double star n m S , disajikan pada Gambar 3.
Gambar 3. Graf double star n m S , .
Teorema 3. Diberikan graf double star n m S , dengan jumlah titiknya m n  maka kekuatan total tak reguler titik totalnya adalah
. 2 1 ) ( ,        m n S tvs n m
Bukti. Misalkan  himpunan  titik
} , , , , , , , , , { ) ( 2 1 2 1 , n m n m y y y y x x x x S V    ,
dengan x dan y adalah titik sentral dan himpunan sisi } , , , , , , , , { ) ( 2 1 2 1 , m m y y y xy x x x n m e e e e e e e S E    dengan xy e adalah  garis  dari  dua titik sentral x dan y .
x y 1 x 2 x m x 1 y 2 y n y
Kasus pertama, untuk n m  .
Pelabelan titik ) ( , n m S V dan pelabelan garis ) ( , n m S E adalah sebagai berikut. Akan dilabeli ( ) , ( ) , ( ) ⌊ ⌋ untuk  setiap i x , m i , , 2 , 1   ,  dan
( ) ⌊ ⌋ , untuk  setiap i y , n i , , 2 , 1   .  Selain  itu,  labeli ( ) ⌈ ⌉ ,
untuk setiap i x e , m i , , 2 , 1   , ( ) ⌈ ⌉ , untuk setiap i y e , n i , , 2 , 1   , dan ( ) ⌊ ⌋ .
Kasus kedua untuk n m  .
Akan dilabeli ( ) , ( ) , ( ) ⌊ ⌋ untuk setiap i x , 1 , , 2 , 1   m i  ,
dan ( ) ⌊ ⌋ , untuk setiap i y , n i , , 2 , 1   dan ( ) ⌊ ⌋ . Selain itu, labeli ( ) ⌈ ⌉ ,  untuk setiap i x e , 1 , , 2 , 1   m i  , ( ) ⌈ ⌉ ,  untuk setiap i y e , n i , , 2 , 1   , dan ( ) ⌊ ⌋ .
Kasus ketiga untuk n m  .
Akan  dilabeli ( ) , ( ) , ( ) ⌊ ⌋ untuk  setiap i x , m i , , 2 , 1   ,
dan ( ) ⌊ ⌋ , untuk  setiap i y , 1 , , 2 , 1   n i  dan ( ) ⌊ ⌋ .  Selain itu,  labeli ( ) ⌈ ⌉ ,  untuk setiap i x e , m i , , 2 , 1   , ( ) ⌈ ⌉ ,  untuk setiap i y e , 1 , , 2 , 1   n i  , dan ( ) ⌊
⌋ .
Oleh  karena  bobot  setiap  titik  berbeda,  maka  terbukti  kekuatan  total  tak  reguler
titik totalnya adalah .
2 1 ) ( ,        m n S tvs n m □

## 4. KESIMPULAN DAN SARAN
Kekuatan  total  tak  reguler  titik  total  dari  graf ladder  rung adalah
graf caveman adalah dan graf double star adalah       2 1 m n .

## 16 Nugroho Arif Sudibyo dan Siti Komsatun

## UCAPAN TERIMAKASIH
Penulis mengucapkan terima kasih kepada Kemenristek Dikti yang telah mendanai penelitian ini pada tahun 2018.

## DAFTAR PUSTAKA
Bača,  M.,  Jendrol,  S.,  Miller,  M.,  dan  Ryan,  J., On  irregular  total  labeling ,
Discrete Mathematics , 307 (2007), 1378-1388.
Ball,  W. W. R.  dan  Coxeter,  H. S. M., Mathematical  Recreations  and  Essays, 13th ed., Dover, New York, 1987.
Gallian,  J.A., A  Dynamic  Survey  of  Graph  Labeling ,  The  electronic  journal  of combinatorics, 18 (2017), 1-432.
Nurdin,  Baskoro,  E.  T.,  Salman,  A.N.M.,  dan  Gaos,  N.N., On  the  total  vertex irregularity strength of trees, Discrete Mathematics , 310 (2010), 3043-3048. Rosa, A. dan Kotzig, A., Magic Valuations of Finite Graphs, Canad. Math. Bull, (1970), 451-461.
Watts,  D. J., Networks,  Dynamics,  and  the  Small-World  Phenomenon ,  Amer.  J. Soc., 105 (1999), 493-527.
Wijaya, K. , Slamin, Surahmat, dan Jendrol’, S., Total Vertex Irregular Labelings of  Complete  Bipartite  Graphs ,  Journal  of  Combinatorial  Mathematics  and Combinatorial Computing, 55 (2005), 129-136.
Wijaya, K. dan Slamin., Total Vertex Irregular  Labelings of  Wheels,  Fans, Suns and  Friendship  Graphs ,  Journal  of  Combinatorial  Mathematics  and Combinatorial Computing, 56 (2008), 103-112.