Page 110 - Trends in Science and Technology fo Sustainable Living

Trends in Science and Technology 71
for Sustainable Living

1. Bilangan Terhubung Pelangi Beberapa Kelas Graf Umum
Pada tahun 2008, Chartrand dkk. telah memperoleh bilangan
terhubung pelangi beberapa kelas graf umum sebagai berikut.

Lema 1. (Chartrand dkk., 2008)
Misalkan G adalah graf terhubung non-trivial berukuran m.
(1) G = K adalah graf lengkap jika dan hanya jika rc(G) = src(G)
n
= 1;
(2) G = T adalah graf pohon dengan m = n-1 jika dan hanya
n
jika rc(G) = src(G) = m;
(3) Jika G = C adalah graf lingkaran dengan n ≥ 4, maka
n
n
rc ()G = src ()G =  ;


2
(4) Jika G = W adalah graf roda dengan n ≥ 3, maka
n
 1, jikan = 3;
 
rc ( )G =  2, jika 4 ≤ n ≤ 6;
 3, jika n ≥ 7.
 
n
dan src ()G = 


3
(5) Misalkan G = K adalah graf bipartit dengan s dan t adalah
s,t  
bilangan asli, maka rc ( )G = min     s  t    ,4   jika 2 ≤ s ≤ t , dan

src ()G =   s  t jika 1 ≤ s ≤ t .


(6) Misalkan G = K n ,n , ,n adalah graf p-partit lengkap
1 2 p p− 1
dengan p ≥ 3 dan n ≤ n ≤ ≤  n sehingga s = ∑ n dan
1 2 p i
i 1 =
t = n , maka
p

 1, jikan = 1;
  p
( ) =
rc G  2, jika n ≥ p 2 dan s > ; t
   jika s ≤
 min  s  t  ,3 ,  . t
       