E-Jurnal Matematika Vol. 7 (1), Januari 2018, pp. 36-40

DOI: https://doi.org/10.24843/MTK.2018.v07.i01.p182

ISSN: 2303-1751

TOTAL EDGE IRREGULARITY STRENGTH DARI GRAF Kn - {e}

Muardi1§, Qurratul Aini2, Irwansyah3

§Corresponding Author

ABSTRACT

In this paper we determine the total edge irregularity strength of Kn- {e}, that is a complete graph in which one of its edge has been removed. To do so, we make three cases. In two cases, the labelling of Kn- {e} equals to the labelling of the complete graph Kn such that no re-labelling is necessary. Meanwhile, the third case could not happen. As a result, the total edge irregularity strength of Kn — {e} equals to the total edge irregularity strength of Kn.

Keywords: Complete graph, labelling, total edge irregularity strength.

  • 1.    PENDAHULUAN

Pelabelan didefinisikan sebagai suatu pemberian nilai (dengan bilangan bulat positif atau bilangan bulat non-negatif) pada titik, sisi, atau keduanya sehingga memenuhi kondisi tertentu. Pelabelan yang sering digunakan yaitu pelabelan titik, pelabelan sisi, dan pelabelan total (pelabelan titik dan sisi). Pelabelan graf pertama kali diperkenalkan oleh matematikawan yang bernama Sedlacek pada tahun 1964, pelabelan graf merupakan pemberian label yang berupa bilangan bulat positif pada elemen-elemen dalam graf yang berupa sisi dan titik.

Termotivasi oleh hal tersebut, Ba c a dkk (2001) memperkenalkan pelabelan total tak beraturan. Pelabelan total tak beraturan yaitu pelabelan graf dengan minimal mempunyai dua titik dan satu sisi yang melabeli setiap sisi dan titik pada graf dengan bilangan bulat positif. Pelabelan total tak beraturan ini terbagi dalam dua jenis, yaitu pelabelan total sisi (total edge irregularity strengh) tak beraturan dan pelabelan total titik tak beraturan (total vertex irregularity strengh). Pelabelan graf yang akan dibahas dalam penelitian ini adalah pelabelan total sisi tak beraturan.

Definisi 2.1 (Ivanco dan Jendrol, 2010) Misalkan G = ( V,E) merupakan graf sederhana. Pelabelan total tak beraturan f: {1,2, ^, k} → V(G) ∪ E(G)      merupakan

pelabelan pada simpul dan verteks G sehingga berlaku

w t (xy) ≠ w t(x' y ) dengan

w t (xy) = f(x) + f(xy) + f (y)

Nilai k terkecil yang mengakibatkan terdapat pelabelan total tak beraturan f: {1,2, ^, k} → V(G) ∪E(G) disebut sebagai total edge irregularity strength dari G , dan dinotasikan dengan t e s (G) (Ivanco dan Jendrol, 2010).

Selanjutnya, hubungan antara     ( )

dengan jumlah sisi dan derajat maksimal graf diberikan dalam teorema berikut.

Teorema 2.1 (Ba c a dkk, 2007) Misalkan G = (V,E) merupakan graf dengan himpunan titik ( ) dan tidak kosong himpunan sisi ( ), maka

■ j ≤ t e s( G) ≤ ∣E∣


Teorema 2.2 (Ba ĉ a dkk, 2007) Misalkan G=(V,E) merupakan graf dengan nilai derajat maksimal Δ=Δ(G), maka

Δ+1 tes (G)≥⌈2⌉

Dari Teorema 2.1 dan Teorema 2.2 diperoleh bahwa :

|E(G)|+2  Δ+1

tes (G)≥maks{⌈    3    ⌉,⌈ 2 ⌉}

Selain itu, Ba ĉ a, dkk. (2001), telah mendapatkan tes (G) pada beberapa kelas graf seperti graf lintasan Pn, graf lingkaran Cn, graf bintang Sn, graf roda Wn, dan graf friendship Fn. Jendrol, dkk. (2010) juga telah mengkaji mengenai tes (G) untuk graf lengkap Kn . Mengacu pada hasil tersebut, pada paper ini tes (G ) akan dikembangkan untuk graf Kn -{e}, yaitu graf lengkap lengkap Kn yang diambil salah satu sisinya.

  • 2.    HASIL DAN PEMBAHASAN

    • 2.1    Pelabelan Total Sisi Tak Beraturan Graf

      Lengkap Kji

Secara umum, langkah-langkah untuk mendapatkam total edge irregularity strength pada grap lengkap ( Kn), adalah sebagai berikut: 1. Membagi verteks menjadi 3 himpunan

A,B,C , dimana :

|A|=|B|=⌊? ⌋ dan | G|=n-|A|-|B|

Contoh : A ={a,b}  , B ={c,f} ,

C={d,e}

  • 2.    Melabeli verteks yang ada di A dengan 1.

  • 3.    Melabeli verteks yang ada di C dengan |E(G)|+2

3

λ =⌈


⌈( 2-1)+2

3

Γn2 -n+4 =⌈    6    ⌉.

  • 4.    Melabeli sisi yang di E(A,A ) sehingga bobotnya ada di [3,(|2|)+2]   dengan

E(A,A) merupakan himpunan semua sisi

yang menghubungkan verteks di A dengan verteks di A.

  • 5.    Melabeli sisi yang ada di E(C,C) sehingga bobotnya ada di [3λ-(|f|)+1,3λ]

  • 6.    Melabeli sisi yang ada di E(A,B ) sehingga bobotnya ada di [(| |)+3,(| |)+3+ |A||B|-1].

  • 7.    Melabeli sisi yang ada di E(C,B) sehingga bobotnya ada di [3λ-(|f|)-|B||C|+ 1,3'l -(|f|)].

  • 8.    Melabeli sisi yang ada di E(A,C ) dan E(B,B) sehingga bobotnya ada di [(| 2|)+ 3+|A||B|,3A-(|f|)-|B||C|].

Misalnya diberikan graf lengkap Ke berikut.

Gambar 1. Graf lengkap Ke

Jumlah total sisi diberikan oleh rumus n(n-1)

| EKn|=        untukKn ,n≠5

Dengan demikian total edge irregularity strength dari Gambar 1 disajikan dalam Gambar 2 berikut.

Gambar 2. Graf lengkap Ke dengan tes (G)=6

Dalam melakukan pelabelan total sisi tak beraturan pada graf lengkap Kn ada beberapa hal yang harus diperhatikan :

  • 1.    Label terendah 1 dan tertinggi λ.

  • 2.    Bobot terendah 3 dan tertinggi 3A.

  • 3.    Banyaknya bobot yang tersedia adalah 3λ-3+1=3λ-2.

  • 4.    Ada 3 kasus untuk | EKn | , yaitu

  • a.  | EKn|=3A-2

  • b.    | EKn|+1=3A-2

  • c.    | EKn|+2=3A-2

  • 2.2 Pelabelan Total Sisi Tak Beraturan Graf

    Lengkap Kn-{e}

Selanjutnya, untuk graf Kn-{e}, diasumsikan tes (G)=A. Jadi,

  • ≥     {⌈ E(G)|+2  Δ+1

  • ≥      {⌈          ⌉,⌈     ⌉}

Tanpa mengurangi keumuman, dimisalkan :

|E|+2 3

λ =⌈


Dibagi 3 kasus untuk nilai | E| :

  • 1. |E|+2=3λ↔|E|=3λ-2

  • 2. | E|+2+1=3A↔|E|+1=3λ-2

  • 3. |E|+2+2=3λ↔|E|+2=3λ-2

Dengan mengingat bahwa banyaknya bobot yang tersedia jika label maksimumnya A adalah 3A-2, maka dipunyai 3 kasus berikut.

  • •    Kasus (1): banyaknya sisi = banyaknya bobot

  • •  Kasus (2): banyaknya sisi = banyaknya

bobot – 1

  • •  Kasus (3): banyaknya sisi = banyaknya

bobot – 2

  • 2.2.1    Pelabelan Total Sisi Tak Beraturan Pada Kasus (1) dan (2)

Diambil beberapa sampel graf lengkap Kn-{e } dengan | EKn | yang memenuhi kasus (1) dan kasus (2) berikut ini.

Gambar 3. (a) Graf lengkap ^2 dan (b) Graf lengkap K2 -{e}


Pada Gambar 3, (a) adalah graf lengkap ^2 dengan label maksimal 1 dan (b) adalah graf lengkap ^2 -{e} dengan label maksimal 1.

  • (a)    Untuk | EK2|=1

  • 1    = ⌈| - |3+2⌉ =⌈|1|3+2⌉

A=1

  • (b)    Untuk | EK2 -{e}|=|EK2|-1=0 λ=⌈|1 |3+2 ⌉ =⌈|0|3+2⌉

=1

Pelabelan pada ^2 -{e } adalah sama dengan pelabelan di ^2 .

Jadi, tidak perlu dilakukan pelabelan ulang.

Gambar 4. (a) Graf lengkap ^3 dan (b) Graf lengkap ^3 -{e}

Pada Gambar 4, (a) adalah graf lengkap ^3 dengan label maksimal 2 dan (b) adalah graf lengkap ^3 -{e} dengan label maksimal 2.

  • (a)    Untuk | EK3|=3

λ = ⌈| - |3+2⌉

=⌈|3|3+2⌉

=2

  • (b)    Untuk | EK3 -{e}|=|EK2|-1=2

λ=⌈|i|3+2⌉

|2|+2

λ=⌈  3  ⌉

λ=2

Pelabelan pada K^ -{e} adalah sama dengan pelabelan di K^ .

Jadi, tidak perlu dilakukan pelabelan ulang.

Pelabelan pada ^4 -{e } adalah sama dengan pelabelan di ^4 . Jadi, tidak perlu dilakukan pelabelan ulang.

Teorema 2.1 Secara umum, untuk kasus (1) dan kasus (2) pelabelan terhadap K∏-{e} adalah sama dengan pelabelan terhadap Kn .

Bukti :

Kasus (1) : |E|=3λ-2

|E|+2

⟷3=λ

⌈| E- |-31+2⌉= λ

Jadi, berdasarkan Teorema 2.1, tes ( Kn -

{e})=λ=    ( Kn).     █


Gambar 5. (a) Graf lengkap K2^ dan (b) Graf lengkap Ka-{e}


Pada Gambar di atas (a) adalah graf lengkap ^4 dengan label maksimal 3 dan (b) adalah graf lengkap ^4 -{e} dengan label maksimal 3.


  • (a)    Untuk | EK^|=6

λ = ⌈| - |3+2⌉

=⌈|6|3+2⌉

=3

  • (b)    Untuk |EK4-{e}|=|EK4|-1=5 λ =⌈|e |3+2⌉

=⌈|5|3+2⌉

=3


  • 2.2.2 Pelabelan Total Sisi Tak Beraturan pada Kasus (3)

Kasus (3) tidak dapat terjadi. Sebagai contoh, diinterpretasikan kasus (1), kasus (2) dan kasus (3) dalam mod 3 seperti berikut :

  • •    Kasus (1) : |E|≡1mod 3

  • •    Kasus (2) : | E|≡0mod 3

  • •    Kasus (3) : |E|≡2mod 3

Teorema 4.2 | EKn|= -(^) mod3=

  • 1    mod 3 {0 mod 3

Bukti :

  • (i)    Jika salah satu diantara n atau n-1 habis dibagi 3, maka:

n(n-1) --mod3=0mod 3

  • (ii)    Jika salah satu diantara n atau n-1 kongruen dengan 1 mod 3, maka :

  • a.    n≡1mod 3

Akibatnya n-1≡0mod 3 Kembali ke kasus (i).

  • b.    n-1≡1mod 3

Akibatnya n≡2mod 3

Ditulis : n=3k+2

n-1=3k+2-1=3k+1 n(n-1)=(3k+2)(3k+1) =9k2+3k+6k+2


Untuk k genap ⟶ k=2l

n(n-1)=9x4I2 +6+12l+2

n(n-1)=18I2 +3l+6l+1 ≡(0+0+0+1)mod 3

Untuk k ganjil ⟶ k=2l+1

k2 =4I2 +4l+1

n(n-1)=9(4I2 +4l+1)+3(2l+1) +6(2l+1)+2

=36I2 +36l+9+6l+3+12l+6+2 =36I2+36l+6l+12l+12l+20 n(n-1)     ,

2   =18I2+18l+3l+6l+10

≡(0+0+0+0+1)mod 3

  • (iii)    Jika salah satu dari n atau n-1 kongruen dengan 2 mod 3, maka : a. n≡2mod 3

n-1≡1mod 3 Kembali ke kasus (ii) b. n≡0mod 3

n-1≡2mod 3 Kembali ke kasus (i).

Jadi, tidak ada kasus (3).

█

Bukti dari Teorema 2.2, menjelaskan bahwa tidak ditemukan kasus yang menyebabkan ⌈| EKn | r1+2⌉=⌈| | ⌉-1 sehingga tes ( Kn -{e}) selalu sama dengan tes ( Kn).

  • 3.    KESIMPULAN

Berdasarkan hasil dan pembahasan, dapat disimpulkan bahwa secara umum, pelabelan terhadap Kn-{e} adalah sama dengan pelabelan terhadap Kn . Selain itu, karena tidak ditemukan kasus yang menyebabkan ⌈| EKn | ;1+2⌉=⌈|EKn | ⌉-1,makates ( Kn -{e}) selalu sama dengan tes ( Kn).

  • 4.    SARAN

Kajian ini diharapkan dapat memperkaya keilmuan matematika, khususnya materi tentang pelabelan total sisi tak beraturan pada graf dan disarankan dapat dikembangkan untuk teori graf yang lebih lanjut.

Daftar Pustaka

Bača, M., Jendrol, S., Mirka, M., dan Ryan, J.. 2007. On Irregular Total Labellings. Discrete Mathematics. Vol. 307, hal. 13781388.

Jendrol, S., Mižkuf, J., dan Sotăk, R.. 2010. Total Edge Irregularity Strength of Complete Graphs and Complete Bipartite Graphs. Discrete Mathematics. Vol. 310, hal. 400-407.

40