## Bilangan Terhubung-Total Pelangi untuk Beberapa Graf Amalgamasi
Arbain Universitas Sembilanbelas November Kolaka email:  arbaindjingga@gmail.com
Abstrak
Semua  graf  yang  dikaji  pada  tesis  ini  adalah  graf  hingga,  sederhana,  dan  tak berarah.  Misalkan ! = ! ("!( ), #( )) adalah  graf  terhubung  tak  trivial.  Fungsi $ % !"!( )!& !#( ) ! ' ! {1, 2, . . . , *} untuk  suatu *! + - dikatakan  pewarnaan- * -total pelangi  pada ,  jika  untuk  setiap  dua  titik / dan 0 di "!( )  terdapat  lintasan /! 3 !0 dengan  setiap  sisi  dan  titik  dalam  pada  lintasan  tersebut  memperoleh  warna  berbeda. Lintasan  yang  seperti  itu  dinamakan  lintasan-total  pelangi.  Graf disebut  terhubung- total pelangi jika untuk setiap dua titik / dan 0 di "!( ) terdapat lintasan-total pelangi /! 3 !0 .  Bilangan  terhubung-total  pelangi  dinotasikan  dengan 45$( ) ,  dideﬁnisikan sebagai  banyak  warna  minimal  yang  dibutuhkan  untuk  membuat  graf bersifat terhubung-total  pelangi.  Misalkan 4 adalah  bilangan  asli  dengan 4! 6! 2.  Misalkan { 7 !|8! + ! [1, 4]} adalah  koleksi  berhingga  graf  terhubung  tak  trivial  dan  setiap 7 mempunyai  titik  tetap 9 :7 .  Graf  amalgamasi 7 dinotasikan  dengan ;<>?( 7 !, 9 :7 !, 4) adalah  graf  yang  dibentuk    dengan  merekatkan  semua  graf 7 pada  titik 9 :7 .  Titik 9 :7 disebut sebagai titik terminal. Dalam tesis ini ditentukan batas  bawah  dan  batas  atas bilangan  terhubung-total  pelangi  untuk graf   amalgamasi.       Selanjutnya ditentukan bilangan  terhubung-total  pelangi  graf  amalgamasi  tertentu,  yakni  graf  pohon  dan lengkap.
Kata kunci : graf amalgamasi, terhubung-total pelangi.

## 1. PENDAHULUAN
Konsep dari keterhubungan pelangi pada graf pertama kali diperkenalkan oleh Chartrand dkk.  pada  tahun  2008  dikutip  dari    Chartrand,  G  dkk  (2008).  Sejak  pertama  kali diperkenalkan,  konsep  keterhubungan  pelangi  mengalami  perkembangan.  Konsep  ini telah menarik perhatian dan hingga kini telah banyak makalah yang dipublikasikan terkait hal  ini.  Misalkan ! = ! @"!( ), #( )A adalah  graf  terhubung  tak  trivial.  Dideﬁnisikan suatu  pewarnaan ! "#($) % " {1, 2". . . , &} untuk  suatu &" ' * dikatakan  pewarnaan- & pelangi pada $ , jika untuk setiap pasang titik +, -" ' "/"($) terdapat suatu lintasan +" 0 "- yang  setiap  sisinya  memperoleh  warna  berbeda.  Lintasan  tersebut  dinamakan  lintasan pelangi. Graf $ dikatakan terhubung pelangi, jika untuk setiap pasang titik +, -" ' "/"($) terdapat lintasan pelangi +" 0 "- . Bilangan terhubung pelangi graf $ , dinotasikan dengan 3 ($) adalah  banyak  warna  minimal  yang  dibutuhkan  sehingga $ bersifat  terhubung pelangi.
Parameter  graf  yang  telah  dijelaskan  oleh  Chartrand  dkk.  dideﬁniskan  untuk pewarnaan  sisi  pada  graf.  Krivelevich  dan  Yuster  (2010)  dalam  Krivelevich,  M.  dan
Yuster,  R.  (2010)    memperkenalkan  parameter  baru  yang  berhubungan  dengan  bilangan terhubung  pelangi  yang  dideﬁnisikan  untuk  pewarnaan  titik  pada  graf.  Suatu  pewarnaan ! "/"($) " % " {1, 2". . . , &} untuk  suatu &" ' * disebut  pewarnaan- & -titik  pelangi  pada $ , jika untuk  setiap pasang titik +, -" ' "/"($) terdapat suatu  lintasan +" 0 "- dengan  setiap titik  dalam  pada  lintasan  tersebut  memperoleh  warna  berbeda.  Lintasan  yang  seperti  itu dinamakan  lintasan-titik  pelangi  .  Graf $ dikatakan  terhubung-titik  pelangi,  jika  untuk setiap  pasang  titik +, -" ' "/"($) terdapat  lintasan-titik  pelangi +" 0 "- .  Bilangan terhubung-titik pelangi graf $ , dinotasikan dengan 34 ($) adalah banyak warna minimal yang dibutuhkan sehingga $ bersifat terhubung-titik pelangi.
Uchizawa  dkk  (2011)  memperkenalkan  varian  lain  dari  konsep  keterhubungan pelangi,  yaitu  terhubung-total  pelangi.  Misalkan & adalah  bilangan  asli.  Fungsi ! "/"($) " 5 "#($) " % " {1, 2". . . , &} dikatakan pewarnaan- & -total pelangi pada $ , jika untuk setiap  pasang  titik +, -" ' "/"($) terdapat  lintasan +" 0 "- dengan  setiap  sisi  dan  setiap titik  dalam  pada  lintasan  tersebut  memperoleh  warna  berbeda.  Lintasan  yang  seperti  itu dinamakan lintasan-total pelangi. Graf $ disebut terhubung-total pelangi jika untuk setiap pasang titik +, -" ' "/"($) terdapat lintasan-total pelangi +" 0 "- . Bilangan terhubung-total pelangi  dinotasikan  dengan 63 ($) ,  dideﬁnisikan  sebagai  banyak  warna  minimal  yang dibutuhkan untuk membuat graf $ bersifat terhubung-total pelangi. Sun  (2013)  dan Liu dkk (2014) juga melakukan penyelidikan terkait konsep ini dan memperoleh hasil berikut. Lemma    1.1 (Liu,    2014). Misalkan $ graf  terhubung  tak  trivial  berorde  n  dan berdiameter 789:($) ,  maka
a. 63 ($) "" = ""1"" ; ""$ adalah  graf  lengkap;
b. 2789:($) " 0 "1"" < ""63 ($) "" < ""2>" 0 "? . Proposisi  1.2 (Liu, 2@1A ). Jika $ graf  terhubung  berorde  n  dengan  q  titik  mempunyai derajat  paling  sedikit 2 ,  maka 63 ($) " < ">" 0 "1" B "C .  Persamaan  berlaku  jika  dan hanya jika $ graf pohon .
Liu  dkk.  (2014)  [4],  juga  melakukan  penyelidikan  tentang  bilangan  terhubung- total pelangi  untuk graf lingkaran D> , graf roda E> , dan graf bipartit  lengkap F G,H . Dalam      makalah      ini      dibahas      berupa      batas      bawah      dan      batas    atas bilangan terhubung-total pelangi untuk graf amalgamasi. Selanjutnya ditentukan bilangan terhubung-total pelangi untuk graf amalgamasi untuk kelas graf pohon dan graf lengkap. Pada bagian ini, dideﬁnisikan [9, I] " = " {+" ' "J|9" < "+" < "I}.

## 2. HASIL UTAMA
Misalkan 6" ' * dengan 6" K "2 . Untuk 8" ' " [1, 6] , Misalkan $ L adalah graf terhubung tak trivial, |/"($8")| " = " > L , > L ' * dengan > L " K "2 . Misalkan {$ M ", $ N ", . . . , $ O "} adalah koleksi berhingga graf terhubung tak trivial dan setiap $8 , mempunyai titik tetap 4 PL . Graf Amalgamasi $ L dinotasikan dengan Amal ($ L ", 4 PL ", 6) adalah graf yang dibentuk dengan merekatkan semua graf $ L pada titik 4 PL . Titik 4 PL disebut sebagai titik terminal  dalam Fitriani dan Salman (2016)  .
Misalkan $"" Q ""R:9S($ L ", 4 PL ", 6) ,  dengan 4 PL " = ""4 . Deﬁnisikan /"($) "" = ""{4} " 5 " {4 L , T"|8" ' " [1, 6], T" ' " [1, & L 0 1]} . Sebagai contoh, lihat  Gambar  1.
Gambar  1 Amalgamasi  graf ! ", # , dan $
Berikut   disajikan   batas   bawah   dan   batas   atas   bilangan   terhubung-total pelangi  untuk  graf  amalgamasi.
Teorema 2.1. Misalkan %" & ', %" ( "2 . Misalkan { ) "|*" &"[1, %]} adalah koleksi berhingga graf terhubung tak trivial dan setiap ) mempunyai titik tetap + -) . Jika " . ""/0345 ) , + -) , %6 , maka 27*305 6 8 1" 9 "%:;5 6 "9 1 <"= %:;5 ) 6 > )?! .
Bukti . Pertama, dibuktikan %:;5 6 "( "27*305 6 8 1 . Berdasarkan Lemma 1.1 yang disajikan  pada  Bab  II,  diperoleh %:;5 6 ( 27*305 6 8 1 . Selanjutnya,  ditunjukkan
%:;5 6 9 "1 <"= %:;5 ) 6 > )?! @
Misalkan A ) ′ suatu pewarnaan- %:;5 ) "6 -total pelangi pada ) . Deﬁnisikan pewarnaan A B "C"5 6"D "E5 6"F"[1, 1 <"= %:;5 ) 6
> )?! ] dengan aturan sebagai berikut.
· A5G6 H I" A ! ′ 5G6"""""""""""""""""""""""""""""
A J ′ 5G6 < = %:;K L M JN! L?! " 1 < = %:;K L M > L?! """"""""" O · A5P6 H Q A ! ′ 5P6""""""""""""""""""""""""""""" "A J ′ 5P6 < = %:;K L M JN! L?! O Pandang sebarang dua titik berbeda R, S" & "C"5 6 . Kasus 1 "R, S" & "C"5 ) 6 untuk *"" &""[1, %]
Terdapat lintasan-total pelangi R" 8 "S oleh pewarnaan A yang bersesuaian dengan A ) ′ @ Kasus 2 R" & "C5 ) 6 dan S" & "C5 T 6 . Untuk  i & [1, t]  dan  j & [1, t]  dengan  i  =  j. Terdapat lintasan-total pelangi R" 8 "+ dan +" 8 "S oleh pewarnaan A yang bersesuaian secara berturut-turut dengan A ) U dan A T U , dengan + adalah titik di yang bersesuaian dengan titik terminal + -) .  Misalkan V ! H "R" 8 "+ , V # H "+" 8 "S ,  dan V ! D V # H R 8 +, +" 8 "S , yakni lintasan R 8 S yang melalui titik + . Karena pewarnaan-total pelangi ) berbeda untuk setiap *" &"[1, %] , diperoleh R 8 +, + 8 S adalah suatu lintasan-total pelangi R 8 S . Karena itu, A adalah pewarnaan-total  pelangi pada .  Jadi, %:;5 6 "9 "1 < = %:;5 ) 6 > )?! .
Teorema 2.2. Misalkan %, W, dan X adalah bilangan bulat dengan % ( 2 serta W & [Y, %] dan X & [Y, %] sedemikian sehingga W < X H %
. Misalkan . /0345 *, + -) ", %6 dengan ) , * & [1, %] adalah sebarang graf pohon. Jika ) yang mempunyai titik
jika ! "(# $ );
jika ! "%# & ' dan * ! [2, +] jika = - .$ = -
jika / ! 0(# 1 );
jika / ! 0%# & ' dan * ! [2, +]
terminal berderajat satu ada sebanyak 343 dan # $ yang mempunyai titik terminal berderajat sedikitnya dua ada sebanyak * , maka bilangan terhubung-total pelangi graf #
adalah
+56(#) = 7 8 9 (: $ < 7) < 7 8 7 < * 8 9 5 $ 3 > $?1 > $?1 33= 7 8 9 (: $ < 7) < * 8 9 5 $ > $?1 > $?1 = 7 < * 8 9 : $ < 7 8 5 $ > $?1 = 7 < * 8 9 +56(#) > $?1
Sebagai ilustrasi, disajikan contoh pewarnaan 7 < * 8 9 +56(# $ ) > $?1 -total pelangi  pada
graf amalgamasi pohon @ABC(# $ , 3- .$ , +) dengan + = D dan * = 2 pada  Gambar 2.
Gambar  2:   Pewarnaan- 22 -total  pelangi  pada @ABC(# $ , - .$ , +)
Teorema 2.3. Misalkan : dan + adalah bilangan asli dengan :3 E 3F dan +3 E 32 . Untuk G3 !3[7, +] , Misalkan # H @ABC(I J $ , - .$ , +) , dengan I $ J adalah graf lengkap I J berorde : .   Bilangan  terhubung-total pelangi graf # adalah
+56(#) = K3+ 8 7333 :+ L3+ = 2, F; M333333 :+ L3+ E D N Bukti. Dideﬁnisikan  himpunan  titik  dan  himpunan  sisi  graf sebagai  berikut. !( ) = {"}#$#{" %,& |' * [1, +] dan - * [1, .] }  dan /( ) = {"" %,& |'# * [1, +] dan - * [1, .]} $ {" %,0 " %,2 |' * [1, +] dan 3, 4 * [1, .], 3 5 #4} .
Mudah diperiksa bahwa diameter adalah 6'78( ) = 9 . Pembuktian  dibagi  menjadi  dua  kasus  sebagai  berikut. Kasus 1 +# = #9, : Pertama,  ditunjukkan +;<( ) ##> ##+# ? #1 . Karena 6'78( ) #= 9 , diperoleh +;<( ) > +# ? 1 = : untuk + = 9 . Andaikan +;<( ) #@ #: untuk + = : ,  maka  terdapat A suatu  pewarnaan- : -total  pelangi pada . Pandang dua titik berbeda " %,0 , " &,2 * !( ) dengan ', - * [1, :] dan 3, 4 * [1, .] . Lintasan " %,0 B#" &,0 dengan  panjang  tidak  lebih  dari  diameter  hanyalah " %,0 "" &,2 .  Dari sini,  jelas  bahwa A(" %,0 ) 5 A(") untuk  setiap '# *#[1, :] dan 3 * [1, .] .  Tetapkan  suatu warna  untuk  titik " ,  sehingga  tersisa  2  warna  untuk  mewarnai  sisi "" %,0 , ' * [1, :], 3 *
[1, .] .  Sebarang  pewarnaan  sisi-sisi "" %,0 , ' * [1,:], 3 * [1, .] menggunakan 9 warna,
jika C = " %,0 , ' * [1, +], 3 * [1, .]
jika C = " jika D = " %,0 " %,2 , ' * [1, +] dan 3, 4 * [1, .] ; jika D = "" %,0 , ' * [1, +] dan 3 * [1, .] terdapat ', -# * [1, :] dan 3, 4 * [1, .] sedemikian  sehingga  sisi "" %,0 , "" &,2 memperoleh warna  yang  sama.  Akibatnya  tidak  ada  lintasan-total  pelangi " %,0 B " &,2 .  Hal  ini bertentangan dengan pengandaian +;<( ) #@ #: untuk +# = #: .  Haruslah +;<( ) #> #+# ? #1# = #E untuk + = : .
Selanjutnya,  ditunjukkan +;<( ) @ #+ ? 1 .  Misalkan C * !( ) dan D * /( ) . Deﬁnisikan pewa rnaan <F !( ) $ /( ) G [1, + ? 1] dengan aturan sebagai berikut.
· <(C) = H#1####### #+ ? 1 I
· <(D) = H#1#'I
Jelas  bahwa  sebarang  dua  titik  bertetangga J, K * !( ) terdapat  lintasan-total    pelangi J B K yaitu JK .    Untuk  dua  titik  berbeda  tidak  bertetangga,  yaitu " %,0 , " &,2 dengan
', - * [1, +], ' 5 - dan 3, 4 * [1, .] ,  lintasan-total  pelangi " %,0 B " &,2 adalah " %,0 "" &,2 . Karena itu, +;<( ) @ #+ ? 1 untuk + = 9, : .
Kasus 2 +# > #E . Pertama,  ditunjukkan +;<( ) > L untuk + > E .  Andaikan +;<( ) @ E ,  maka  terdapat A suatu  pewarnaan- E -total  pelangi  pada .  Dengan  cara  yang  serupa  seperti  pada  kasus 1 untuk + = : diperoleh suatu kontradiksi. Jadi terbukti +;<( ) > L untuk + > E . Selanjutnya,  ditunjukkan +;<( ) @ L .  Misalkan C * !( ) dan D * /( ) .  Deﬁnisikan pewarnaan <F !( ) $ /( )#G [1, L] dengan aturan sebagai berikut.
· <(C) = H#: #L I · <(D) = M #1 #9 #E I
Jelas  bahwa  sebarang  dua  titik  bertetangga J, K * !( ) terdapat  lintasan-total  pelangi J B K , yaitu JK . Perhatikan dua titik berbeda J, K * !( ) yang tidak bertetangga.
(1) J = " %,0 dan K = " &,2 . Untuk ' * [1, +], - * [1, +], 3 * [1, .] , dan 4 * [1, .] dengan 3 dan 4 mempunyai varitas sama, terdapat lintasan-total pelangi " %,0 B " &,2 , yaitu " %,0 "" &,2NO " &,2 .
(2) J = " %,0 dan K = " &,2 .
Untuk ' * [1, +], - * [1, +], 3 * [1, .] ,  dan 4 * [1, .] dengan 3 dan 4 berbeda  varitas, terdapat  lintasan-total  pelangi " %,0 B " &,2 ,  yaitu
" %,0 "" &,2 . Jadi  terbukti +;<( ) @ L untuk + > E . jika C = " %,0 , ' * [1, +], 3 * [1, .]
jika C = " jika D = "" %,0 , ' * [1, +] dan ' ganjil; 3 * [1, .] ;
jika D = "" %,0 , ' * [1, +] dan ' genap; 3 * [1, .] jika D = " %,0 " &,2 , ', - * [1, +]# dan 3, 4 * [1, .]
Untuk  ilustrasi,  disajikan    pewarnaan- E -total  pelangi  pada  graf  amalgamasi  lengkap P874(Q R % , " S% , +) dengan . = L dan +# = #: serta  pewarnaan- L -total  pelangi  pada P874(Q R % , " S% , +) dengan . = L dan + = E seperti pada Gambar 3.
Gambar 3 (a) Pewarnaan-4-total pelangi pada P874(Q T % , " S% , +)
(b) Pewarnaan-5-total pelangi pada P874(Q R % , " S% , +)

## DAFTAR PUSTAKA
Chartrand,  G.,  Johns,  G.L.,  McKeon, K.A.,  dan  Zhang,  P.  (2008):  Rainbow    connection in  graphs, Math Bohemica , 133 ,  85-98.
Fitriani, D. dan Salman, A.N.M. (2016): Rainbow connection number of amalgamation of some graphs, AKCE International Journal Graphs and Combinatorics , 13 , 90-99. Krivelevich,  M.  dan  Yuster,  R.  (2010):  The  rainbow  connection  of  graph  in  (at  most) reciprocal to its minimum degree, J. Graph Theory , 63 , 185- 191 Liu,  H.,  Mestre,  A.,  dan  Sousa,  T.  (2014):   Total  rainbow  k-connection  in graphs,
Discrete  Applied  Mathematics , 174 , 92-101.
Sun,  Y.  (2013):   On  two  variants  of  rainbow  connection, WSEAS  Transactions  on Mathematics , 12 ,  266-272.
Uchizawa,    K.,    Aoki,    T.,    Suzuki,    A.,    dan    Zhou,    X.    (2011):      On    the    rainbow connectivity  of  graph, Complexit  and  FPT  Algorithms , 6842 ,  86-97.