Dimensi k-Metrik pada Graf Mushroom dan Graf Path Corona Graf Double Fan

Oleh :
Arum Veliana - M0119014 - Fak. MIPA

Graf G adalah suatu himpunan tak kosong berhingga V(G) = {v1,v2,..., vn}yang setiap elemennya disebut vertex dan himpunan E(G) = {e1,e2,...,en} yangmerupakan himpunan pasangan tidak berurutan dari anggota-anggota V(G),yang setiap elemennya disebut edge. Perkembangan penelitian dalam bidangteori graf yang semakin pesat telah memunculkan berbagai konsep baru, salahsatunya adalah dimensi k-metrik. Metode yang digunakan dalam penelitian iniadalah kajian pustaka dengan mengumpulkan dan mempelajari berbagai sumberyang relevan, seperti jurnal ilmiah, buku, dan tulisan ilmiah yang dimuat padasitus web.Diberikan graf terhubung dan sederhana G = (V(G),E(G)) serta bilanganbulat positif k. Himpunan S ⊆ V(G) disebut pembangkit k-metrik pada grafG jika untuk setiap pasang vertex berbeda, yaitu u,v ∈ V(G), terdapat palingsedikit k vertex w1,w2,w3,...,wk∈ S sedemikian sehingga d(u,wi) ̸= d(v,wi)untuk setiap i ∈ {1,2,...,k}. Jarak terpendek antara vertex u ke v dinotasikandengan d(u,v). Basis k-metrik adalah pembangkit k-metrik yang memiliki kardi-nalitas minimum. Selanjutnya, dimensi k-metrik pada graf G, yang dinotasikandengan dimk(G), adalah kardinalitas dari basis k-metrik pada graf G.Graf mushroom yang dinotasikan dengan Mrm,nmerupakan graf yang di-bentuk dari graf null, graf path, dan satu titik pusat, dengan setiap vertex padagraf null dan graf path dihubungkan ke titik pusat tersebut. Graf double fan me-rupakan graf yang dibentuk dari penjumlahan graf complete 2K1dan graf pathPn, yang dinotasikan dengan dFn= 2K1+ Pn. Corona dari graf G dan grafH, yang dinotasikan dengan GJH, merupakan graf yang dibentuk dari graf Gdan |V(G)| salinan graf H, yaitu H1,H2,...,H|V(G)|. Selanjutnya, setiap vertexui∈ V(G) dihubungkan dengan setiap vertex pada V(Hi) menggunakan sebuahedge untuk setiap 1 ≤ i ≤ |V(G)|.Hasil penelitian menunjukkan bahwa dimensi k-metrik dari graf mushroomadalah dim2(Mrm,n) = n + ⌈2m5− 1⌉ dengan m,n ≥ 2. Selanjutnya, dimensik-metrik dari graf path corona graf double fan adalah dim2(PmJdFn) = 2 ×(⌈1 +n3⌉) untuk m = 2 dan 2 ≤ n ≤ 6.iv