J. D IFERENSIAL / E -ISSN:2775-9644
Vol.6(1),2024, 52–56
doi: https://doi.org/10.35508/jd.v6i1.12526

## A RTIKEL P ENELITIAN

## Dimensi Metrik Campuran pada Graf Double Fan
Deddy Rahmadi 1
1 Program Studi Matematika, UIN Sunan Kalijaga, Yogyakarta-Indonesia
* Penulis korespondensi: deddy.rahmadi@uin-suka.ac.id
Diterima: 07 September 2023; Direvisi: 08 November 2023; Disetujui: 11 November 2023; Dipublikasi:09 Februari 2024.
Abstrak : Misal G = ( V ( G ) , E ( G )) adalah graf sederhana. Suatu titik x ∈ V ( G ) merupakan pembeda dari elemen u, v ∈ V ( G ) ∪ E ( G ) jika d ( x, u ) ̸ = d ( x, v ) . Dimensi metrik campuran, baru saja diperkenalkan. Dimensi metrik campuran ( mdim ( G ) ) pada graf G adalah kardinalitias terkecil dari himpunan titik yang merupakan pembeda dari setiap pasang elemen dari V ( G ) ∪ E ( G ) . Pada penelitian ini, akan diidentifikasi dimensi metrik campuran pada graf double fan .
Kata Kunci: dimensi metrik campuran, teori graf, basis metrik campuran, graf double fan
Abstract : Let G = ( V ( G ) , E ( G )) be a simple connected graph. A vertex x ∈ V ( G ) resolves the elements u, v ∈ V ( G ) ∪ E ( G ) if d ( x, u ) ̸ = d ( x, v ) . The mixed metric dimension, has been recently introduced. The mixed metric dimension ( mdim ( G ) ) of a graph G is the cardinality of a smallest set of vertices that resolves each pair of elements from V ( G ) ∪ E ( G ) . In this paper, we will identify the mixed metric dimension on double fan graph.
Keywords: mixed metric dimension, graph theory, mixed metric basis, double fan graph

## 1. Pendahuluan
Diberikan G = ( V ( G ) , E ( G )) adalah graf terhubung dan sederhana, dengan V ( G ) merepresentasikan himpunan elemen yang disebut titik dan E ( G ) merepresentasikan himpunan elemen yang disebut sisi. Dimensi metrik campuran pada suatu graf diperkenalkan oleh [1] . Kajian ini, merupakan campuran antara dimensi metrik dan dimensi metrik sisi.
Pada graf terhubung G , jarak antara dua titik u dan v adalah panjang dari lintasan terpendek antara titik u dan v pada graf G . Suatu titik w merupakan pembeda dari titik u, v ∈ V ( G ) jika d ( u, w ) ̸ = d ( v, w ) . Koordinat metrik r ( v, S ) dari titik v terhadap himpunan titik terurut S = { w 1 , w 2 , . . . , w k } yang didefinisikan r ( v, S ) = ( d ( v, w 1 ) , d ( v, w 2 ) , . . . , d ( v, w k )) . Himpunan S merupakan himpunan pembeda jika setiap dua titik u dan v dari G yang dibedakan paling sedikit oleh satu titik di S . Basis metrik dari graf G adalah himpunan pembeda dengan kardinalitas terkecil. Dimensi metrik pada graf G adalah kardinalitas dari basis metrik yang dinotasikan dim ( G ) . Slater [2] dan Harary Melter [3] mengenalkan himpunan pembeda pada graf. Beberapa penelitian yang dipublikasikan terkait penerapan dan sifat teoritis dimensi metrik. Penerapan pada bidang robotika, dianalisis pada [4] dan penerapan pada bidang kimia dipaparkan pada [5] dan [6] . Secara umum, terdapat beberapa perkembangan dari dimensi metrik: dimensi metrik kuat [7] , dimensi metrik lokal [8] , dimensi k-metrik [7] , dan lain-lain.
Jarak antara titik w dan sisi uv pada graf G didefinisikan sebagai d ( uv, w ) = min { d ( u, w ) , d ( v, w ) } . Titik w membedakan dua sisi e, f ∈ E ( G ) jika d ( w, e ) ̸ = d ( w, f )) . Koordinat metrik r ( e, S ) dari sisi e terhadap himpunan titik terurut S = { w 1 , w 2 , . . . , w k } yang didefinisikan r ( v, S ) = ( d ( e, w 1 ) , d ( e, w 2 ) , . . . , d ( e, w k )) . Himpunan S merupakan himpunan pembeda jika setiap dua sisi e dan f dari E ( G ) yang dibedakan paling sedikit oleh satu titik di S . Basis metrik sisi dari graf G adalah himpunan pembeda dengan kardinalitas terkecil. Dimensi metrik pada graf G adalah kardinalitas dari basis metrik yang dinotasikan dim E ( G ) . Konsep tentang dimensi metrik sisi diperkenalkan oleh Kelenc et al [9] .
Misalkan V ( G ) ∪ E ( G ) adalah gabungan semua himpunan titik dan sisi pada graf G . Titik v merupakan pembeda dari elemen di V ( G ) ∪ E ( G ) jika d ( a, v ) ̸ = d ( v, b ) untuk a, b ∈ V ( G ) ∪ E ( G ) . Koordinat metrik r ( a, S ) dari a terhadap himpunan titik terurut S = { w 1 , w 2 , . . . , w k } yang didefinisikan r ( v, S ) = ( d ( a, w 1 ) , d ( a, w 2 ) , . . . , d ( a, w k )) . Himpunan S dikatakan sebagai himpunan pembeda campuran jika setiap dua elemen dari G dibedakan oleh paling sedikit satu titik di S . Basis metrik campuran dari graf G adalah himpunan pembeda campuran dengan kardinalitas terkecil. Dimensi metrik campuran dari graf G adalah kardinalitas dari basis metrik campuran yang dinotasikan sebagai dim M ( G ) .
Konsep dari dimensi metrik campuran sudah diperkenalkan oleh Kelenc et al. [1] . Pada penelitian ini, dimensi metrik campuran telah diterapkan pada beberapa kelas graf, yaitu graf lintasan, graf cycle , graf pohon, graf grid, dan graf bipartit lengkap. Nilai eksak dari dimensi metrik campuran dari graf unicyclic dan batas atas dari graf yang memuat subgraf unicyclic dijelaskan pada [10] .
Penelitian mengenai dimensi metrik pada graf double fan diberikan pada Teorema 1.1 yang dikaji oleh Silalahi dan Mulyono pada [11] dan dimensi k-metrik diberikan oleh Rahmadi pada [12] .
Teorema 1.1. Misal f 2 ,n adalah graf double fan. Untuk setiap bilangan asli n ≥ 2 , maka
dim ( f 2 ,n ) = 2 n +7 5 , n = 5 i + 4 , i ≥ 0; ⌈ 2 n +2 5 ⌉ , n ̸ = 5 i + 4 , i ≥ 0 .
Selanjutnya pada penelitian ini, dimensi metrik campuran akan dikaji pada kelas graf double fan .

## 2. Metode Penelitian
Metode penelitian yang digunakan adalah menerapkan konsep dimensi metrik campuran pada kelas graf double fan dengan urutan
1. Menentukan jarak antar titik pada graf double fan .
2. Menentukan jarak antar setiap titik dan sisi pada graf double fan 3. Menentukan himpunan pembeda campuran.
4. Memperoleh basis metrik campuran.
5. memperoleh nilai dimensi metrik campuran pada graf double fan .

## 3. Hasil dan Pembahasan
Graf double fan yang dinotasikan f 2 ,n adalah graf yang diperoleh dari join graf null dengan dua titik dan graf path dengan n titik. Gambar graf double fan f 2 ,n diilustrasikan pada Gambar 3.1 . Dari Gambar 3.1 terlihat bahwa graf double fan f 2 ,n memiliki n + 2 titik.
u 1
v 1 v 2 v 3 v n u 2
Gambar 3.1: Graf double fan f 2 ,n
Berikut diberikan tabel jarak setiap dua titik pada graf double fan yang disajikan dalam Tabel 3.1 .
Tabel 3.1: Jarak setiap dua titik berbeda pada graf f 2 ,n
Jarak u 1 u 2 v 1 v 2 v 3 v 4 . . . v n u 1 0 2 1 1 1 1 . . . 1 u 2 2 0 1 1 1 1 . . . 1 v 1 1 1 0 1 2 2 . . . 2 v 2 1 1 1 0 1 2 . . . 2 v 3 1 1 2 1 0 1 . . . 2 v 4 1 1 2 2 1 0 . . . 2
.. . .. . .. . .. . .. . .. . .. . .. . .. .
v n 1 1 2 2 2 0 . . . 0
Berikut diberikan proposisi, lema dan teorema mengenai dimensi metrik campuran pada graf double fan .
Bagian berikutnya dibahas mengenai sifat teoritis dari dimensi metrik, dimensi metrik sisi, dan dimensi metrik campuran.
Untuk sebarang graf G , berlaku
dim M ( G ) ≥ max { dim ( G ) , dim E ( G ) }
Proposisi 3.1. Misal v adalah sebarang titik di graf G dan S = V ( G ) −{ v } . Jika untuk setiap titik w ∈ N ( v ) , terdapat x ∈ S , berlaku d ( vw, x ) ̸ = d ( w, x ) , dengan S adalah himpunan pembeda campuran pada graf G .
Lebih lanjut, akan ditentukan nilai dari dimensi metrik campuran pada graf tersebut. Untuk titik- titik pada graf double fan , dapat dipartisi menjadi V 1 = { u 1 , u 2 } dan V 2 = { v 1 , v 2 , . . . , v n } . Selanjutnya, berikut diberikan beberapa lema yang akan digunakan untuk membuktikan Teorema 3.1 .
Lema 3.1. Jika S adalah sebarang himpunan pembeda campuran dari graf double fan, maka | S | ≥ n + 1 .
Bukti . Graf double fan f 2 ,n memiliki n + 2 titik. Andaikan | S | < n + 1 , diperoleh n + 2 | S | kemungkinan nilai S . Dengan demikian diperoleh semua kemungkinan himpunan S yang dituangkan dalam beberapa pola berikut.
1. S 1 = { u 1 , v 1 , v 2 , . . . , v k } untuk k ∈ { 1 , 2 , ..., n − 1 } . 2. S 2 = { u 2 , v 1 , v 2 , . . . , v k } untuk k ∈ { 1 , 2 , ..., n − 1 } . 3. S 3 = { u 1 , u 2 , v 1 , v 2 , . . . , v k } untuk k ∈ { 1 , 2 , ..., n − 2 } .
4. S 4 = { v 1 , v 2 , . . . , v k } untuk k ∈ { 1 , . . . , n } .
Kemudian, diberikan tabel yang untuk menjelaskan bahwa setiap kemungkinan himpunan S 1 , S 2 , S 3 , dan S 4 bukan merupakan himpunan pembeda campuran.
Tabel 3.2: Kemungkinan himpunan S yang bukan himpunan pembeda campuran pada graf f 2 ,n
Kemungkinan Himpunan S Kesimpulan S 1 = { u 1 , v 1 , v 2 , . . . , v k } untuk k ∈ { 1 , 2 , ..., n − 1 } r ( v 4 v n − 1 | S 1 ) = r ( v 4 v n | S 1 )
S 2 = { u 2 , v 1 , v 2 , . . . , v k } untuk k ∈ { 1 , 2 , ..., n − 1 } r ( u 1 v n − 1 | S 2 ) = r ( u 1 v n | S 2 ) S 3 = { u 1 , u 2 , v 1 , v 2 , . . . , v k } untuk k ∈ { 1 , 2 , ..., n − 2 } r ( u 1 v n − 1 | S 3 ) = r ( u 1 v n | S 3 ) S 4 = { v 1 , v 2 , . . . , v k } untuk k ∈ { 1 , . . . , n } r ( u 1 | S 4 ) = r ( u 2 | S 4 )
Untuk setiap elemen pada graf double fan , diperoleh r ( a | S ) = r ( b | S ) , terjadi kontradiksi, dengan demikian | S | ≥ n + 1 .
Teorema 3.1. Misalkan f 2 ,n adalah graf dengan n ≥ 2 , maka dim M ( f 2 ,n ) = n + 1 .
Bukti . Untuk sebarang nilai n ≥ 2 , dipilih S = { u 1 , u 2 , v 1 , v 2 , . . . v n } , diperoleh metrik representasi sebagai berikut:
r ( u 1 | S ) = (0 , 2 , 1 , 1 , . . . , 1 , 1); r ( u 2 | S ) = (2 , 0 , 1 , 1 , . . . , 1 , 1); r ( v 1 | S ) = (1 , 1 , 0 , 2 , . . . , 2 , 2); r ( v 2 | S ) = (1 , 1 , 1 , 1 , . . . , 2 , 2);
.. . .. . r ( v n − 1 | S ) = (1 , 1 , 2 , 2 , . . . , 1 , 1);
r ( v n | S ) = (1 , 1 , 2 , 2 , . . . , 2 , 0);
r ( u 1 v i | S ) = (0 , 1 , . . . , 1 , 0 , 1 , . . . , 1); untuk i = 1 , 2 , . . . , n ;
r ( u 2 v i | S ) = (1 , 0 , 1 , . . . , 1 , 0 , 1 , . . . , 1); untuk i = 1 , 2 , . . . , n ;
r ( v i v n ) = (1 , 1 , 0 , 1 , . . . , 1 , 0 , 1 . . . , 1); untuk i = 1 , 2 , . . . , n − 2; r ( v i v i +1 ) = (1 , 1 , . . . , 1 , 0 , 0 , 1 , . . . , 1); untuk i = 1 , 2 , . . . , n ;
r ( v i v j ) = (1 , 1 , . . . , 0 , 1 , . . . , 0 , 1)
Diperoleh bahwa setiap metrik representasi berbeda, dengan demikian S adalah himpunan pembeda campuran, jadi S ≤ n +1 . Berdasarkan Lema 3.1 , S adalah basis metrik campuran dan dimensi metrik campuran dari graf double fan adalah n + 1 .

## 4. Kesimpulan
Pada penelitian ini, telah diteliti dimensi metrik campuran pada graf double fan . Pertama diberikan Lema dan Proposisi yang mendukung untuk membuktikan Teorema 3.1 . Telah dibuktikan bahwa dim M ( f 2 ,n ) = n +1 . Lebih lanjut, penulis memberi saran untuk melanjutkan penelitian terkait dimensi metrik campuran pada beberapa kelas graf khusus dan dimensi metrik sisi dari graf double fan dan dipandang dari sisi komputasi.

## Referensi
[1] A. Kelenc, D. Kuziak, A. Taranenko, and I. G. Yero, “Mixed metric dimension of graphs,” Appl. Math. Comput. , vol. 314, pp. 429–438, 2017. View online .
[2] P. J. Slater, “Leaves of trees,” Congr , vol. 14, pp. 549–559, 1975. View online .
[3] F. Harary and R. A. Melter, “On the metric dimension of a graph,” Ars Combin , vol. 2, pp. 191– 195, 1976. View online .
[4] S. Khuller, B. Raghavachari, and A. Rosenfeld, “Landmarks in graphs,” Discrete Appl. Math , vol. 70, pp. 217–229, 1996. View online .
[5] M. Johnson, “Structure-activity maps for visualizing the graph variables arising in drug design,” J Biopharm Stat. , vol. 3, pp. 203–236, 2007. View online .
[6] G. Chartrand, C. Poisson, and P. Zhang, “Resolvability and the upper dimension of graphs,” Comput. Math. Appl. , vol. 39, pp. 19–28, 2000. View online .
[7] A. Seb ¨ o and E. Tannier, “On metric generators of graphs,” Math. Oper. Res. , vol. 29, pp. 383–393, 2004. View online .
[8] F. Okamoto, B. Phinezy, and P. Zhang, “The local metric dimension of a graph,” Math. Bohemica , vol. 135, pp. 239–255, 2010. View online .
[9] A.Kelenc, N.Tratnik, and I.G.Yero, “Uniquely identifying the edges of a graph: The edge metric dimension,” Discrete Appl. Math. , vol. 251, pp. 204–220, 2018. View online .
[10] J.Sedlar and R. ˘ S krekovski, “Mixed metric dimension of a graphs with edge disjoint cycles,” Discrete Appl. Math. , vol. 300, pp. 1–8, 2021. View online .
[11] R.Silalahi and Mulyono, “Metric dimensions and partition dimensions of a multiple fan graph,” Formosa Journal of Science and Technology , vol. 2, pp. 81–88, 2023. View online .
[12] D.Rahmadi and Y. Susanti, “The k-metric dimension of double fan graph,” Journal of Innovation and Technology in Mathematics and Mathematics Education , vol. 2, pp. 31–35, 2022. View online .
textcolorjdFormat Sitasi IEEE: Rahmadi, "Dimensi Metrik Campuran pada Graf Double Fan" , Jurnal Diferensial , vol. 6(1), pp. 52-56, 2024.
This work is licensed under a Creative Commons “Attribution- ShareAlike 4.0 International” license.