Vol.16, No. 1, 10-18, July 2019 doi: 10.20956/jmsk.v%vi%i.5788
*Program Studi Pascasarjana (S2) Matematika, FMIPA-UNHAS Email address: 1 winda.aritonang94@gmail.com, nurdin1701@unhas.ac.id,
3 amirkamalamir@yahoo.com

## NILAI TOTAL KETIDAKTERATURAN-H PADA GRAF C n x P 3
Winda Aritonang 1* , Nurdin Hinding 2* , Amir Kamal Amir 3*

## Abstract
To  determine  of  H-irregularity  total  strength  in  all  graphs  was  not  complete  on  graph  classes.  The research aims to determine alghorithm the H-irregularity total strength of graph C n x P 3 for n ≥ 3 with use H-covering, where H is isomorphic to C 4 . The determine of H-irregularity total strength of graph C n x P 3 was conducted by determining lower bound and smallest upper bound. The lower bound was analyzed  based  on  graph  characteristics  and  other  supporting  theorem,  while  the  upper  bound  was analyzed  by  edge  labeling  and  vertex  labeling  of  graph  C n x  P 3 .The  result  show  that    the  H- irregularity total strength of graph ths(C n x P 3, C 4 )= ⌈ ⌉ for n ≥ 3.
Keywords : H-covering, H-irregularity total strength

## Abstrak
Penentuan nilai total H- ketidakteraturan dari semua graf belum dapat dilakukan secara lengkap. Penelitian ini bertujuan untuk menentukan nilai total ketidakteraturan-H pada graf C n x P 3 untuk n ≥ 3. Penentuan nilai total ketidakteraturan-H  pada  graf  C n x  P 3 dengan  menentukan  batas  bawah  terbesar  dan  batas  atas  terkecil.  Batas bawah  dianalisis  berdasarkan  sifat-siat  graf  dan  teorema  pendukung  lainnya.  Sedangkan  batas  atas  dianalisa dengan pemberian label pada titik dan sisi pada graf C n x P 3 .Berdasarkan hasil penelitian ini diperoleh nilai total ketidakteraturan-H pada graf (C n x P 3, C 4 )= ⌈ ⌉ dengan n ≥ 3.
Kata kunci : Selimut-H, Nilai total ketidakteraturan-H

## 1. Pendahuluan
Graf  adalah  pasangan  dua  buah  himpunan  yaitu  himpunan  titik  dan  himpunan  sisi,  dinotasikan dengan (    ) di mana V menyatakan himpunan titik yang tak kosong dan E adalah himpunan sisi  yang  merupakan  pasangan  tak  terurut  dari  titik-titik V .  Pelabelan  graf  merupakan  suatu  topik dalam teori graf. Objek kajiannya  berupa graf yang secara umum direpresentasikan dengan titik dan sisi,  dan  himpunan  bagian  bilangan  yang  disebut  label.  Pelabelan  graf  adalah  suatu  fungsi  dengan domain himpunan titik dan himpunan sisi atau keduanya dengan range nya bilangan riil.
Salah  satu  jenis  pelabelan  tidak  teratur  lainnya  adalah    pelabelan  total  tidak  teratur ( - Irreguler  total  labelling ).  Pelabelan  jenis  ini  melibatkan  konsep  selimut  graf.  Pelabelan  ini  di perkenalkan oleh Baca dkk. Secara umum pelabelan total tidak teratur- dari suatu graf di definisikan sebagai berikut. Misal adalah suatu graf, selimut sisi dari (e dge covering ) adalah koleksi subgraf dari  graf sedemikian  sehingga  setiap  sisi  dari termuat  dalam  paling  sedikit  satu subgraf dimana
Dalam  hal  ini,  maka disebut  memiliki  selimut  (sisi)-
Winda Aritonang, Nurdin Hinding, Amir Kamal Amir
( ) ( ( ) -( edgecovering ) . Jika setiap subgraf isomorfik dengan suatu graf H, maka dikatakan memiliki suatu selimut- ( - ).
Terdapat  beberapa  hasil  penelitian  terkait  dengan  pelabelan  total tidak  teratur  antara  lain [3]telah  menentukan  nilai  total  sisi  ( )  dan  nilai  total  titik  ( )  pada  graf    kipas,  lintasan  dan ladder.  [3]  telah  menentukan  nilai  total dan tidak  teratur  ( )  pada  graf  planar,  menentukan nilai total tidak teratur ( ) pada graf dan nilai total tidak teratur ( ) pada graf dan merupakan graf  lingkaran dengan titik ( ) dimana merupakan graf Kipas dengan titik  dan graf  Lingkaran  dengan titik.  [1]  telah  menentukan (    ( ) dimana ( ) merupakan banyaknya graf yang di amalgamasi, dan (     ( ) .

## 2. Tinjauan Pustaka
Graf merupakan  suatu  pasangan  himpunan (    ) dinotasikan  dengan (    ) dengan adalah himpunan tidak kosong dari objek-objek yang disebut titik dan adalah himpunan pasangan tidak terurut dari titik-titik berbeda di disebut sisi , - .
Himpunan  titik  pada  Gambar  1  adalah *                      + dan  himpunan  sisinya  adalah *                                  + Selanjutnya  diperoleh  order  dari adalah  8  dan  ukuran  dari adalah 9.
Misalkan ( ( )   ( )) dan ( ( )   ( )) adalah dua buah graf. Graf H disebut subgraf dari G, jika ( )    ( ) dan ( )    ( ) dan dinotasikan dengan . Jika tetapi maka disebut subgraf sejati, dinotasikan dengan , - Perhatikan Gambar 2
Gambar 2 . (a) Graf , (b) Graf (subgraf dari graf )
𝑏 𝑐 𝑎 𝑑 𝑒 𝑓 𝑔 Gambar 1 Graf G 1 v v 2 v 3 1 e 2 e 3 e 4 e v 4 5 e 1 v v 3 3 e 4 e v 4 5 e

## Winda Aritonang, Nurdin Hinding, Amir Kamal Amir
Pada  Gambar  2,  diketahui  bahwa ( )   * , , + dan ( )   * + .  Sedangkan
( )   *
, + dan ( )   * + .  Karena ( )    ( ) dan ( )    ( ) ,  maka merupakan subgraf dari graf .
Graf lintasan dengan n titik adalah graf terhubung yang terdiri atas tepat 2 titik berderajat 1 dan titik berderajat dua [2].
v 1 v 2 v 3 v 4 v 5
Graf  lingkaran  adalah  graf  terhubung  dengan  n  buah  titik  yang  setiap  titiknya  berderajat  dua.  Graf lingkaran dinotasikan dengan dimana [7].
v 1 v 2 v 3 v 4 v 6 v 5
Gambar 4 Graf Lingkaran
Misalkan dan adalah  graf  dengan ( )   * + dan ( )   * + maka adalah graf dengan himpunan titik (     )    ( )    ( ) dan e= ( )( ) adalah sisi dari
jika dan hanya jika memenuhi satu dari dua item berikut i dan ( ) atau dan ( ) [6].
v 1 v 2 v 3 u 2 u 1 ( ( ( ( ( ( u 1 u 2 u 2 u 1 u 2 u 1 , v 1 v 1 v 3 v 3 v 2 v 2 ) ) ) ) ) ) , , , , , ( a ) ( b ) ( c )
Gambar 5 (a) Graf (b) Graf (C) Graf Misal merupakan suatu graf dengan , untuk suatu bilangan bulat positif , merupakan subgraf-subgraf  dari .  Koleksi ,  ditulis  ( )  disebut  selimut  sisi  ( edge covering )  dari ,  jika  setiap  sisi  dari termuat  dalam  paling  sedikit  satu  subgraf dimana
,  dan  dikatakan mempunyai  suatu  selimut  sisi-( )  ( ( )- edge covering ).  Misalkan mempunyai  suatu  selimut  sisi-(
),  jika  setiap  subgraf ( ) isomorfik dengan graf , maka dikatakan mempunyai selimut- ( - covering ) [3].
Gambar 3. Graf Lintasan 𝑃

## Winda Aritonang, Nurdin Hinding, Amir Kamal Amir
Pada tahun 2017 [3] telah menentukan batas bawah nilai total ketidakteraturan- untuk sebarang graf , seperti yang ditulis pada Teorema 1.
Teorema  1: Misalkan adalah  graf  yang  mempunyai  selimut- dengan  banyaknya subgraf    yang isomorfik dengan , maka
(    )   ⌈ | ( )|   | ( )| ⌉
Dimana | ( )| dan | ( )| masing-masing  merupakan  banyaknya  titik  dan  banyaknya  sisi  pada subgraf .  Misalkan suatu  graf  yang  memuat - selimut  dengan  banyaknya  subgraf yang isomorfik  dengan . dinyatakan  sebagai  pelabelan- total  tidak  teratur dari  graf dengan (    ) . Bobot subgraf terkecil dari pelabelan- total adalah | ( )|   | ( )| .

## 3. Nilai Total Ketidakteraturan-H pada Graf
Himpunan titik dan himpunan sisi graf , untuk bilangan bulat positif adalah sebagai berikut : ( )   * |              + ( )   * |              + * |              +
Dengan menggunakan himpunan titik dan himpunan sisi tersebut, maka didefinisikan himpunan titik dan himpunan sisi dari subgraf di sebagai berikut:
Untuk 𝑉(𝐻 𝑖 )   *𝑥 𝑖 𝑦 𝑖 𝑥 𝑖 𝑦 𝑖 + 𝐸(𝐻 𝑖 )   *𝑥 𝑖 𝑦 𝑖 𝑥 𝑖 𝑥 𝑖 𝑥 𝑖 𝑦 𝑖 𝑦 𝑖 𝑦 𝑖 +
Gambar 6 Graf 𝐶 𝑛 𝑃

## Winda Aritonang, Nurdin Hinding, Amir Kamal Amir
Untuk dengan
Teorema 2.6.2 Misalkan adalah graf dengan maka, ( )   ⌈ ⌉ Bukti : Untuk  membuktikan  bahwa  ths ( )   ⌈ ⌉ maka  akan  dibuktikan  ths ( )
⌈ ⌉ .  Untuk  membuktikan  ths ( )   ⌈ ⌉ ,  maka  digunakan  Teorema  2.6.1  yaitu ths (
⌈ | ( )| | ( )| ⌉ dengan t adalah banyaknya subgraf H.
Perhatikan  bahwa  banyaknya  subgraf  C 4 dari adalah  2n  dan | ( )| dan | ( )| . Jadi ths ( )   ⌈ ⌉ Selanjutnya  akan  ditentukan  bahwa ( )   ⌈ ⌉ .  Untuk  membuktikan  bahwa (
)   ⌈ ⌉ ,  maka  akan  dikonstruksi  suatu  fungsi  pelabelan  ketidakteraturan  C 4 total  pada sebagai berikut:
( )   { ⌈ ⌉
⌈ ⌉ ( )   { ⌈ ⌉
⌈ ⌉ ( )   { ⌈ ⌉ ⌈ ⌉
𝑉(𝐻 𝑛 )   *𝑥 𝑦 𝑥 𝑛 𝑦 𝑛 + 𝐸(𝐻 𝑛 )   *𝑥 𝑥 𝑛 𝑦 𝑦 𝑛 𝑥 𝑛 𝑦 𝑛 𝑥 𝑦 +
𝑉(𝐻 𝑖 )   *𝑦 𝑖 𝑧 𝑖 𝑦 𝑖 𝑧 𝑖 + 𝐸(𝐻 𝑖 )   *𝑦 𝑖 𝑧 𝑖 𝑦 𝑖 𝑦 𝑖 𝑦 𝑖 𝑧 𝑖 𝑧 𝑖 𝑧 𝑖 + 𝑉(𝐻 𝑛 )   *𝑦 𝑧 𝑦 𝑛 𝑧 𝑛 +
𝐸(𝐻 𝑛 )   *𝑦 𝑧 𝑦 𝑦 𝑛 𝑦 𝑛 𝑧 𝑛 𝑦 𝑧 + 𝑖               ⌊ 𝑛 9 ⌋ 𝑖   ⌊ 𝑛 ⌋       𝑛 𝑖               ⌊ 𝑛 9 ⌋ 𝑖               ⌊ 𝑛 9 ⌋ 𝑖   ⌊ 𝑛 ⌋       𝑛
𝑖   ⌊ 𝑛 ⌋       𝑛 ths ( )   ⌈ ⌉
( )   { ⌈ ⌉
⌈ ⌉  Untuk ganjil ( ) { ⌈ ⌉
⌈ ⌉ ⌈ ⌉ ( ) ( )
{ ⌈ ⌉ ⌈ ⌉ ( ) { ⌈ ⌉ { ⌊ ⌋ ⌈ ⌉ ⌈ ⌉ ( )
 Untuk genap
( )
{ ⌈ ⌉ { ⌈ ⌉ ⌈ ⌉
⌈ ⌉ ( )
( )
{
( ) ⌈ ⌉
⌈ ⌉
𝑖               ⌊ 𝑛 9 ⌋ 𝑖   ⌊ 𝑛 ⌋       𝑛 𝑖               ⌈ 𝑛 ⌉
𝑖   ⌊ 𝑛 ⌋       𝑛
𝑖               ⌈ 𝑛 ⌉ 𝑖   ⌈ 𝑛 ⌉  𝑔𝑒𝑛𝑎𝑝 𝑖   ⌈ 𝑛 ⌉ 𝑔𝑎𝑛𝑗𝑖𝑙 𝑖   ⌊ 𝑛 ⌋       𝑛
𝑖   ⌈ 𝑛 ⌉ 𝑖               ⌊ 𝑛 9 ⌋
𝑖   ⌊ 𝑛 ⌋       𝑛
𝑖             ⌈ 𝑛 ⌉ 𝑖   ⌈ 𝑛 ⌉       𝑛
𝑖               ⌈ 𝑛 ⌉ 𝑖   ⌈ 𝑛 ⌉ 𝑔𝑒𝑛𝑎𝑝 𝑖   ⌈ 𝑛 ⌉ 𝑔𝑎𝑛𝑗𝑖𝑙 𝑖   ⌊ 𝑛 ⌋       𝑛
( ) { ⌈ ⌉ { ⌈ ⌉ ⌈ ⌉
⌈ ⌉ ( )
selanjutnya akan ditunjukkan bahwa bobot setiap subgraf berbeda untuk pada sebagai berikut :
1. Untuk genap
𝑖   ⌈ 𝑛 ⌉ 𝑔𝑒𝑛𝑎𝑝 𝑖   ⌈ 𝑛 ⌉ 𝑔𝑎𝑛𝑗𝑖𝑙 𝑖   ⌊ 𝑛 ⌋       𝑛 𝑖               ⌈ 𝑛 ⌉ ⌈ ⌉       ⌈ ⌉   ⌈ ⌉           ⌈ ⌉ ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉
𝑊 𝑊 𝑡 (𝐻 𝑛 )   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉     ⌈ 𝑛   𝑛 ⌉
𝑊 𝑊 𝑡 (𝐻 𝑛 )   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉ ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉
⌈ ⌉           ⌈ ⌉   ⌈ ⌉           ⌈ ⌉   𝑤 𝑡 (𝐻 )
𝑊 𝑊 𝑡 (𝐻 )   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉       ⌈ 𝑖 ⌉
⌈ ⌉           ⌈ ⌉   ⌈ ⌉           ⌈ ⌉ < ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉       ⌈ 𝑖 ⌉     ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉
⌈ ⌉       ⌈ ⌉       ⌈ ⌉       ⌈ ⌉ = 𝑊 𝑡 (𝐻 𝑛 ) 𝑊 𝑊 𝑡 (𝐻 𝑛 )   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉       ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉
⌈ ⌉       ⌈ ⌉       ⌈ ⌉       ⌈ ⌉ < ⌈ 𝑛 2 ⌉ ⌈ 𝑛 2 ⌉ ⌈ 𝑛 2 ⌉ ⌈ 𝑛 2 ⌉ ⌈ 𝑛 2 ⌉ .⌈ 𝑛 ⌉/ ⌈ 𝑛 2 ⌉ ⌈ 𝑛 2 ⌉ 𝑊 𝑡 (𝐻 𝑛 )
< ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉ ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉
⌈ ⌉   ⌈ ⌉           ⌈ ⌉       ⌈ ⌉   𝑊 𝑡 (𝐻 𝑛 )
⌈ ⌉   ⌈ ⌉           ⌈ ⌉       ⌈ ⌉ < ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉       ⌈ 𝑖 ⌉
2. Untuk ganjil
Berdasarkan maka diperoleh bahwa bobot setiap subgraf berbeda. Karena itu graf dimana memiliki suatu pelabelan- k total tidak teratur sisi, dimana ⌈ ⌉ . Dengan demikian, diperoleh ( )   ⌈ ⌉ . Karena ( )   ⌈ ⌉ dan ( )   ⌈ ⌉ , maka ( )
⌈ ⌉

## Daftar Pustaka
[1]  Agustin,  I.H.,  2017.  On  H-Irregulerity  Strengh  of  Graph:  A  New  Notion. Journal  of  Physic : Confrens Series 855.
[2] Ahmad, A., 2014. Irregular Total Labeling of Disjoint Union of Prisms and Cycles. Australasian Journal of Combinatorics . 59 : 98-106.
⌈ ⌉       ⌈ ⌉   ⌈ ⌉           ⌈ ⌉ < ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉ ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉ < ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉ ⌈ ⌉       ⌈ ⌉   ⌈ ⌉           ⌈ ⌉
⌈ ⌉           ⌈ ⌉   ⌈ ⌉           ⌈ ⌉   𝑤 𝑡 (𝐻 ) < ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉
⌈ ⌉   ⌈ ⌉           ⌈ ⌉       ⌈ ⌉   𝑊 𝑡 (𝐻 𝑛 )
𝑊 𝑊 𝑡 (𝐻 𝑛 )   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉
⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉
𝑊 𝑊 𝑡 (𝐻 𝑛 )   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉ ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉   ⌈ 𝑛   𝑛 ⌉ 𝑊 𝑊 𝑡 (𝐻 )   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉
⌈ ⌉            ⌈ ⌉   ⌈ ⌉           ⌈ ⌉
⌈ ⌉       ⌈ ⌉       ⌈ ⌉       ⌈ ⌉ = 𝑊 𝑡 (𝐻 𝑛 ) 𝑊 𝑊 𝑡 (𝐻 𝑛 )   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉   ⌈ 𝑖 ⌉
⌈ ⌉       ⌈ ⌉       ⌈ ⌉       ⌈ ⌉ < ⌈ 𝑛 2 ⌉ ⌈ 𝑛 2 ⌉ ⌈ 𝑛 2 ⌉ ⌈ 𝑛 2 ⌉ ⌈ 𝑛 2 ⌉ ⌈ 𝑛 2 ⌉ ⌈ 𝑛 2 ⌉ ⌈ 𝑛 2 ⌉ = 𝑊 𝑡 (𝐻 𝑛 )

## Winda Aritonang, Nurdin Hinding, Amir Kamal Amir
[3]  Bača,  M.,  dkk.,  2017.  On  H-Irregulerity  Strengh  of  Graph.  Discucsiones  Mathematics. Graph Theory 37(2017) 1067-1078.
[4]  Baca,  M.,  Jendrol.,  Miller,  M.  dan  Ryan,  J.,  2007. On  Irregular  total  Labelings . Discrere Mathematics . 307 : 1378-1388.
[5]  Indriati D, Widodo, Indah IE dan Sugeng KA., 2015. On Total Irregularity Strength of Double- Star and Related Graphs. Procedia Computer Science 74 Hal 118-123. Elsevier: Indonesia.
[6]  Ramdani  R  dan  Salman  ANM.,  2013.  On  The  Total  Irregularity  Strength  of  Some  Cartesians Product Graphs. Int.J.Graphs Comb .,10 No.2.Page 199-209. AKCE. Bandung : Indonesia.
[7] Tarawneh I, Hasni R. dan Ahmad A., 2016. On the Edge Irregularity Strength of Corona Product of  Cyccle  with  Isolated  Vertices. AKCE  International  Journal  of  Graphs  and  Combinatorics 13.Page 213-217 . Elsevier. Mathematics Science.