Page 121 - Trends in Science and Technology fo Sustainable Living
P. 121
82 Fakultas Sains dan Teknologi
Universitas Terbuka (2023)
d. Graf hasil strong product
Pada tahun 2010, Li dan Sun menyelidiki bilangan terhubung
pelangi graf hasil strong product dari sebarang graf terhubung.
Misalkan G = * G ⊗ G ⊗ ⊗ G ( k ≥ 2 ) dengan setiap G, i ∈ 1,k
1 2 k i
graf terhubung. Oleh karena Cartesian product dari sebarang dua
graf adalah sebuah subgraf merentang dari strong product-nya,
G adalah subgraf merentang dari G*, maka diperoleh hasil berikut.
Lema 2. (Li dan Sun (2010), Li dan Sun (2012))
Misalkan G = * G ⊗ 1 G ⊗ 2 ⊗ G dengan masing-masing G, i ∈ 1,k
k
i
k
* ∑
graf terhubung, maka rc G ) ≤ rc (G i ) .
(
i 1 =
Adapun Gologranca dkk. (2013) memperoleh karakteristik
bilangan terhubung pelangi graf hasil strong product dari sebarang
graf terhubung sebagai berikut.
Teorema 17. (Gologranca dkk., 2013)
Misalkan G dan H graf terhubung, maka
(
(i) rc (G ⊗ H ) ≤ max { ( ),rc G rc H } ) ;
(ii) src (G ⊗ H ) ≤ max { src ( ),G src H } ) .
(
Dari Lema 1 dan Teorema 17 tersebut dapat disimpulkan
bahwa jika diberikan dua graf terhubung yang sama maka
Teorema 17 lebih baik dari Lema 2. Selanjutnya Gologranca dkk.
(2013) menunjukkan bilangan terhubung pelangi graf hasil strong
product dari dua graf bipartit lengkap sebagai berikut.
Teorema 18. (Gologranca dkk., 2013)
Untuk mn 1 mn ⊗ K p ,q ) ≤ 3.
,, ,p q ∈ dengan ,nq > , maka (rc K
,
Pada tahun 2014, Hader menyelidiki bilangan terhubung
pelangi hasil strong product dari graf lingkaran dan kipas dengan
graf lintasan.